几个最短路算法。

http://acm.hdu.edu.cn/showproblem.php?pid=2544
大水题一枚，仅以练手。
Dijkstra:

#include<iostream>
using namespace std;
#define SIZE 200
#define INF 0xfffffff
#define MIN(a,b) a>b?b:a
int G[SIZE][SIZE];
int d[SIZE];
int vis[SIZE];
int N,M;
int minV()
{
    int i,v;
    for(i=0;i<N;i++)
    {
       if(!vis[i])
       {
          v = i;
          break;
       }
    }
    for(;i<N;i++)
    if(!vis[i]&&d[v]>d[i])
    v = i;
    return v;
}
int Dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<N;i++)d[i]=INF;
    d[s] = 0;
    for(int i=0;i<N;i++)
    {
       int v = minV();
       vis[v] = true;
       for(int u=0;u<N;u++)
       {
          if(G[v][u])
          {
            d[u] = MIN(d[u],d[v]+G[v][u]);
          }
       }
    }
    return d[N-1];
}
int main()
{
    while(cin>>N>>M,N||M)
    {
       for(int i=0;i<N;i++)
       for(int j=0;j<N;j++)
       G[i][j] = INF;
       int a,b;
       for(int i=0;i<M;i++)
       {
          int c;
          cin>>a>>b>>c;
          a--,b--;
          if(c<G[a][b])
          G[a][b] = G[b][a] = c;
       }
       cout<<Dijkstra(0)<<endl;
    }
    return 0;
}

Dijkstra+Priority_Queue:

#include<iostream>
#include<queue>
using namespace std;
struct node
{
  int v;
  int dis;
  node(){}
  node(int vv,int diss):v(vv),dis(diss){}
  bool operator<(const node &n) const
  {
       return dis>n.dis;
  }
};
typedef priority_queue<node> PQ;
const int SIZE = 110;
const int INF = 0xfffffff;
int vis[SIZE];
int dis[SIZE];
int G[SIZE][SIZE];
#define MIN(a,b) a>b?b:a
void init()
{
     memset(vis,0,sizeof(vis));
     for(int i=0;i<SIZE;i++)dis[i]=INF;
     for(int i=0;i<SIZE;i++)
     for(int j=0;j<SIZE;j++)
     G[i][j] = INF;
}
int Dijkstra(int s,int n)
{
    dis[s] = 0;
    PQ pq;
    pq.push(node(s,dis[s]));
    for(int i=0;i<n;i++)
    {
       int v;
       do
       {
           if(pq.empty())return INF;
           v = pq.top().v;
           pq.pop();
       }while(vis[v]);
       vis[v] = 1;
       for(int j=0;j<n;j++)
       {
           if(G[v][j])
           {
              dis[j] = MIN(dis[j],dis[v]+G[v][j]);
              pq.push(node(j,dis[j]));
           }
       }
    }
    return dis[n-1];
}
int main()
{
    
    int n,m;
    while(cin>>n>>m,n||m)
    {
        init();
        for(int i=0;i<m;i++)
        {
           int a,b,c;
           cin>>a>>b>>c;
           a--,b--;
           if(G[a][b]>c)
           G[a][b]=G[b][a]=c;
        }
        cout<<Dijkstra(0,n)<<endl;
    }
    return 0;
}

Floyd:

#include<iostream>
using namespace std;
const int SIZE = 110;
int G[SIZE][SIZE];
const int INF = 0xfffffff;
#define rep(n,i) for(int i=0;i<n;i++)
void init(int n)
{
   rep(n,i)
   {
   rep(n,j)G[i][j] = INF;
   }
}
int Floyd(int n)
{
    rep(n,k)
    {
      rep(n,i)
      {
         rep(n,j)
         {
             if(G[i][j]>G[i][k]+G[k][j])
             {
                G[i][j] = G[i][k]+G[k][j];
             }
         }
      }
    }
    return G[0][n-1];
}
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
       int a,b,c;
       init(n);
       rep(m,i)
       {
          cin>>a>>b>>c;
          a--,b--;
          if(G[a][b]>c)
          {
             G[a][b] = G[b][a] = c;
          }
       }
       cout<<Floyd(n)<<endl;
    }
    return 0;
}

Bellman_Ford:

#include<iostream>
using namespace std;
struct Edge
{
   int s,e;
   Edge(){}
   Edge(int ss,int ee):s(ss),e(ee){}
};
const int SIZE = 20010;
Edge edge[SIZE];
int G[110][110];
int d[110];
void init()
{
    for(int i=0;i<110;i++)
    for(int j=0;j<110;j++)
    G[i][j] = 0xfffffff,d[i]=0xfffffff;
}
void Relax(int u,int v)
{
    if(d[v]>d[u]+G[u][v])
    d[v] = d[u]+G[u][v];
}
void Bellman_Ford(int n,int m)
{
   d[0] = 0;
   for(int i=0;i<n-1;i++)
   {
      for(int j=0;j<m;j++)
      Relax(edge[j].s,edge[j].e);
   }  
}
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
       init();
       for(int i=0;i<m;i++)
       {
          int a,b,c;
          cin>>a>>b>>c;
          a--,b--;
          if(G[a][b]>c)
          {
            G[a][b] = G[b][a] = c;
          }
       }
       int cnt = 0;
       for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)
       {
          if(G[i][j]!=0xfffffff)
          {
             edge[cnt].s = i;
             edge[cnt].e = j;
             cnt++;
          }
       }
       Bellman_Ford(n,cnt);
       cout<<d[n-1]<<endl;
    }
    return 0;
}

SPFA:

#include<iostream>
using namespace std;
#include<queue>
#define N 110
#define INF 0xfffffff
int vis[N];
int map[N][N];
int d[N];
void spfa(int s,int n)
{
    memset(vis,0,sizeof(vis));
    memset(d,127,sizeof(d));
    d[s] = 0;
    vis[s] = 1;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
       int v = q.front();
       q.pop();
       vis[v] = 0;
       for(int i=0;i<n;i++)
       {
          if(map[v][i])
          {
              if(map[v][i]+d[v]<d[i])
              {
                 d[i] = map[v][i]+d[v];
                 if(!vis[i])
                 {
                    vis[i] = 1;
                    q.push(i);
                 }
              }
          }
       }
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
        memset(map,0,sizeof(map));
        for(int i=0;i<m;i++)
        {
           int a,b,c;
           cin>>a>>b>>c;
           a--,b--;
           if(map[a][b]==0||map[a][b]>c)
           map[a][b] = map[b][a] = c;
        }                 
        spfa(0,n);
        cout<<d[n-1]<<endl;
    }
    
    return 0;
}