HDOJ 1874 畅通工程续

说点实在的以前很少写图论的，所以这两天都比较实在的复习呢，基础重要着啊，不然以后写复杂的图论了那还不得急死人。dijkstra，总结一个图论经常需要注意的地方，就是在输入边的时候有可能多次输入i->j的边，我们做最短路径的时候选取最小的边。

代码：

#include<iostream>using namespace std;const int INF=0x7fffffff;int dist[205],map[205][205];bool visit[205];int n,m;void init(){     int i,j;     for( i=0; i<n; i++){          for( j=0; j<n; j++)               map[i][j]=INF;          dist[i]=INF;          visit[i]=false;     }}int Dijkstra(int s,int t){    int mim,pt,i;    dist[s]=0;    pt=s;    memset(visit,false,sizeof(visit));    while( true){           visit[pt]=true;           if( pt==t)               break;           for( i=0; i<n; i++)                if( !visit[i]&&map[pt][i]!=INF)                    dist[i]=min(dist[i],dist[pt]+map[pt][i]);           mim=INF;           pt=-1;           for( i=0; i<n; i++){                if( !visit[i]&&mim>dist[i]){                    mim=dist[i];                    pt=i;                }           }           if( pt==-1) break;               }    return (pt==-1? -1:dist[pt]);            }int main(){    int s,t,i,j,x;    while( scanf("%d%d",&n,&m)!=EOF){           init();           while( m--){                  scanf("%d%d%d",&i,&j,&x);                  if( x<map[i][j]) //选取小的边，这里错了一次。以前也遇到过但是没注意。                      map[i][j]=map[j][i]=x;           }           scanf("%d%d",&s,&t);           printf("%d\n",Dijkstra(s,t));          }                return 0;}