poj3463——Sightseeing

44424742

最短路拓展。
详见：
http://blog.csdn.net/leeeyupeng/archive/2010/08/06/5790928.aspx
#include<iostream>#include<cstring>#include<cstring >using namespace std;#define maxcost 100000009int head[1005];int len;int sum,ans;class node{public:int len,v,next;};node g[300050];void add(int a,int b,int c){g[++len].v =b;g[len].len =c;g[len].next =head[a];head[a]=len;} int dist[1005][2],cnt[1005][2],vis[1005][2];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[i][0]=dist[i][1]=maxcost;dist[s][0]=0;cnt[s][0]=1;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];cnt[g[j].v ][1]=cnt[g[j].v ][0];dist[g[j].v][0]=dis;cnt[g[j].v ][0]=cnt[x][0];}else if(dis==dist[g[j].v ][0]){cnt[g[j].v ][0]+=cnt[x][0];}else if(dis<dist[g[j].v ][1]){dist[g[j].v ][1]=dis;cnt[g[j].v ][1]=cnt[x][y];}else if(dis==dist[g[j].v ][1]){cnt[g[j].v ][1]+=cnt[x][y];}}}if(dist[f][1]-dist[f][0]==1)return cnt[f][1]+cnt[f][0];else return cnt[f][0];}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;}