poj3255——Roadblocks

44424742

求次短路，直接套的模板。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxcost 99999999int n,r;class node{public:int v,len,next;};node g[110006*2];int head[5005];int cnt;void add(int a,int b,int c){g[++cnt].v =b;g[cnt].len =c;g[cnt].next =head[a];head[a]=cnt;}int dist[5005][2],vis[5005][2];int dij(int s,int f){int i,j,k,x,y,dis,min;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++)dist[i][0]=dist[i][1]=maxcost;dist[s][0]=0;for(i=1;i<=2*n;i++){min=maxcost;for(j=1;j<=n;j++){if(!vis[j][0]&&min>dist[j][0]){x=j;y=0;min=dist[j][0];}else if(!vis[j][1]&&min>dist[j][1]){x=j;y=1;min=dist[j][1];}}if(min==maxcost) break;vis[x][y]=1;for(j=head[x];j;j=g[j].next ){dis=min+g[j].len;if(dis<dist[g[j].v ][0]){dist[g[j].v ][1]=dist[g[j].v ][0];dist[g[j].v ][0]=dis;}else if(dis<dist[g[j].v ][1]){dist[g[j].v ][1]=dis;}}}return dist[f][1];}int main(){int a,b,c;cin>>n>>r;cnt=0;for(int i=0;i<r;i++){cin>>a>>b>>c;add(a,b,c);add(b,a,c);}cout<<dij(1,n)<<endl;return 0;}