最短路~dijkstra模板

#define oo 2147483647 void dijkstra() { memset(vis,false,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;i++)dis[i]=a[S][i]; vis[S]=true; dis[S]=0; for(int i=1;i<n;i++) { int _min=oo,k=0; for(int j=1;j<=n;j++) if(dis[j]<_min&&!vis[j]) { _min=dis[j]; k=j; } vis[k]=true; for(int j=1;j<=n;j++) if(!vis[j]) dis[j]=min(dis[j],dis[k]+a[k][j]); } }