poj3255——Roadblocks
求次短路，直接套的模板。#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxcost 99999999int n,r;class node{public:int v,len,next;};node g;int head;int cnt;void add(int a,int b,int c){g[++cnt].v =b;g.len =c;g.next =head;head=cnt;}int dist,vis;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=dist=maxcost;dist=0;for(i=1;i<=2*n;i++){min=maxcost;for(j=1;j<=n;j++){if(!vis&&min>dist){x=j;y=0;min=dist;}else if(!vis&&min>dist){x=j;y=1;min=dist;}}if(min==maxcost) break;vis=1;for(j=head;j;j=g.next ){dis=min+g.len;if(dis<dist.v ]){dist.v ]=dist.v ];dist.v ]=dis;}else if(dis<dist.v ]){dist.v ]=dis;}}}return dist;}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;}
页:
[1]