hdu 2680 Choose the best route

it2022-05-06  4

多个起点,一个终点,求最短路,额,一开始三种SPFA都试了一下,用队列实现,用栈实现,唉,都悲剧的TLE了,怎么就没想到呢,把终点变成起点,就只需要调用一次SPFA了,而且,最后在遍历一下,找出路径最短的原先的起点,

#include<iostream> #include<queue> #define MAXINT 9999999 #define MAXN 1010 using namespace std; int vis[MAXN],dis[MAXN],n,num,m; int root[MAXN],cou[MAXN]; struct edge { int u,w,next; }e[MAXN*20]; bool spfa(int s) { for(int i=1;i<=n;i++) dis[i]=MAXINT; dis[s]=0; memset(vis,0,sizeof(vis)); memset(cou,0,sizeof(cou)); vis[s]=cou[s]=1; queue<int> Q; Q.push(s); while(!Q.empty()) { int t=Q.front(),k; vis[t]=0; Q.pop(); for(int j=root[t];j!=-1;j=e[j].next) { k=e[j].u; if(dis[k]>e[j].w+dis[t]) { dis[k]=e[j].w+dis[t]; if(!vis[k]) { vis[k]=1; Q.push(k); cou[k]++; if(cou[k]>n) return 0; } } } } return 1; } int main() { int a,b,c,cas,max1; int en; while(cin>>n>>m>>en) { num=0; max1=MAXINT; memset(root,-1,sizeof(root)); for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&c); e[num].u=a; e[num].w=c; e[num].next=root[b]; root[b]=num++; } spfa(en); cin>>cas; for(int i=0;i<cas;i++) { scanf("%d",&a); if(dis[a]<max1) max1=dis[a]; } if(max1<MAXINT) cout<<max1<<endl; else cout<<-1<<endl; } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/08/14/2138041.html

相关资源:数据结构—成绩单生成器

最新回复(0)