几个最短路算法。

Coco_young

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:aint 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)       {          v = i;          break;       }    }    for(;i<N;i++)    if(!vis&&d[v]>d)    v = i;    return v;}int Dijkstra(int s){    memset(vis,0,sizeof(vis));    for(int i=0;i<N;i++)d=INF;    d = 0;    for(int i=0;i<N;i++)    {       int v = minV();       vis[v] = true;       for(int u=0;u<N;u++)       {          if(G[v])          {            d = MIN(d,d[v]+G[v]);          }       }    }    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[j] = INF;       int a,b;       for(int i=0;i<M;i++)       {          int c;          cin>>a>>b>>c;          a--,b--;          if(c<G[a])          G[a] = G[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:avoid init(){     memset(vis,0,sizeof(vis));     for(int i=0;i<SIZE;i++)dis=INF;     for(int i=0;i<SIZE;i++)     for(int j=0;j<SIZE;j++)     G[j] = INF;}int Dijkstra(int s,int n){    dis = 0;    PQ pq;    pq.push(node(s,dis));    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]>c)           G[a]=G[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[j] = INF;   }}int Floyd(int n){    rep(n,k)    {      rep(n,i)      {         rep(n,j)         {             if(G[j]>G[k]+G[k][j])             {                G[j] = G[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]>c)          {             G[a] = G[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[j] = 0xfffffff,d=0xfffffff;}void Relax(int u,int v){    if(d[v]>d+G[v])    d[v] = d+G[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]>c)          {            G[a] = G[a] = c;          }       }       int cnt = 0;       for(int i=0;i<n;i++)       for(int j=0;j<n;j++)       {          if(G[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 0xfffffffint 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 = 0;    vis = 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])          {              if(map[v]+d[v]<d)              {                 d = map[v]+d[v];                 if(!vis)                 {                    vis = 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]==0||map[a]>c)           map[a] = map[a] = c;        }                         spfa(0,n);        cout<<d[n-1]<<endl;    }        return 0;}