传送门：http://poj.org/problem?id=2387

这是最短路径问题，本题有重边，但是spfa能解决这个问题：

实现代码：

SPFA:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 const int maxv=1005; 9 const int maxe=4005;10 const int INF=1<<20;   //刚这个开小了wrong了几次。11 12 struct Edge{13     int v,w;14     int next;15 };16 17 int head[maxv];18 int dis[maxv],vis[maxv];19 Edge edges[maxe];20 21 int cnt=0;22 void addEdge(int u,int v,int w){23     edges[cnt].v=v;24     edges[cnt].w=w;25     edges[cnt].next=head[u];26     head[u]=cnt++;27 }28 29 void spfa(int s,int n){30     for(int i=0;i<=n;i++){31         dis[i]=INF;32         vis[i]=0;33     }34 35     dis[s]=0;36     queue
          
           q;37 q.push(s);38 vis[s]=1;39 40 while(!q.empty()){41 int u=q.front();42 q.pop();43 44 for(int i=head[u];i!=-1;i=edges[i].next){45 int v=edges[i].v;46 if(dis[v]>dis[u]+edges[i].w){47 dis[v]=dis[u]+edges[i].w;48 49 if(!vis[v]){50 q.push(v);51 vis[v]=1;52 }53 }54 }55 vis[u]=0;56 }57 58 }59 60 int main(){61 int T,n;62 scanf("%d%d",&T,&n);63 memset(head,-1,sizeof(head));64 for(int i=0;i
          
         
        
       
      
     

 Dijkstra实现：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN=10050;const int INF=1<<20;int map[MAXN][MAXN];bool vis[MAXN];int dis[MAXN],pre[MAXN] ;//路径//图的顶点坐标是从1开始的//Dijkstra的邻接矩阵的实现void Dijkstra(int st,int n){    fill(dis,dis+n+1,INF);    memset(vis,0,sizeof(vis));    memset(pre,-1,sizeof(pre));    dis[st]=0;    for(int j=0;j
        
         dis[i]){                Min=dis[i];                k=i;            }        }        if(k==-1) break;        vis[k]=true;        for(int i=1;i<=n;i++)            if(!vis[i]&&dis[i]>dis[k]+map[k][i]){                dis[i]=dis[k]+map[k][i];                pre[i]=k;            }    }}void output(int k){    if(pre[k]==-1){        return;    }    output(pre[k]);    printf("%d ",pre[k]);}int main(){    int T,N;    scanf("%d%d",&T,&N);        for(int i=1;i<=N;i++){            fill(map[i],map[i]+N+1,INF);        }        for(int i=0;i
         
          w){            map[u][v]=w;            map[v][u]=w;            }                    }        Dijkstra(N,N);        printf("%d\n",dis[1]);    return 0;}