poj3463——Sightseeing
最短路拓展。详见：
http://blog.csdn.net/leeeyupeng/archive/2010/08/06/5790928.aspx
#include<iostream>#include<cstring>#include<cstring >using namespace std;#define maxcost 100000009int head;int len;int sum,ans;class node{public:int len,v,next;};node g;void add(int a,int b,int c){g[++len].v =b;g.len =c;g.next =head;head=len;} int dist,cnt,vis;int dij(int n,int s,int f){int i,j,k,x,y,dis,min;memset(cnt,0,sizeof(cnt));memset(vis,0,sizeof(vis));for(i=1;i<=n;i++)dist=dist=maxcost;dist=0;cnt=1;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 ];cnt.v ]=cnt.v ];dist.v]=dis;cnt.v ]=cnt;}else if(dis==dist.v ]){cnt.v ]+=cnt;}else if(dis<dist.v ]){dist.v ]=dis;cnt.v ]=cnt;}else if(dis==dist.v ]){cnt.v ]+=cnt;}}}if(dist-dist==1)return cnt+cnt;else return cnt;}int main(){int n,m,a,b,c,t;int s,f;cin>>t;while(t--){len =0;memset(head,0,sizeof(head));cin>>n>>m;for(int i=1;i<=m;i++){cin>>a>>b>>c;add(a,b,c);}cin>>s>>f;ans=dij(n,s,f);cout<<ans<<endl;}return 0;}
页:
[1]