首页 > 代码库 > hdu2680 Choose the best route 最短路（多源转单源）
hdu2680 Choose the best route 最短路（多源转单源）
此题中起点有1000个，别有20000条。用链式前向星建图，再枚举起点用SPFA的话，超时了。（按理说，两千万的复杂度应该没超吧。不过一般说计算机计算速度 1~10 千万次/秒。也许拿最烂的计算机来卡时间）
有一个技巧，加一个超级源点。也就是加一个点，使得该点连通所有的起点，并且边的权值为0。这个技巧应用蛮多的。网络流、最小树形图都有题目这样做。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;const int N = 1010, M=20010;const int INF = 0x3f3f3f3f;struct node{ int to, w, next;};node edge[M];int head[N], dist[N], outq[N];bool vis[N];int tot;bool SPFA(int s, int n ){ int i,k; for(i=0;i<=n;i++) dist[i]=INF; memset(vis,0,sizeof(vis)); memset(outq,0,sizeof(outq)); queue<int > q; while(!q.empty()) q.pop(); vis[s]=1; dist[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; outq[u]++; if(outq[u]>n) return 0 ; k=head[u]; while(k>=0) { if(dist[edge[k].to]-edge[k].w>dist[u]) { dist[edge[k].to]=dist[u]+edge[k].w; if(!vis[edge[k].to]) { vis[edge[k].to]=1; q.push(edge[k].to); } } k=edge[k].next; } } return 1;}void addedge(int i,int j,int w){ edge[tot].to=j; edge[tot].w=w; edge[tot].next=head[i]; head[i]=tot++;}void init(){ tot=0; memset(head,-1,sizeof(head));}int main(){ //freopen("test.txt","r",stdin); int i,j,k,n,m,t,s; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { init(); while(m--) { scanf("%d%d%d",&i,&j,&k); addedge(i,j,k); } scanf("%d",&k); for(i=0;i<k;i++) { scanf("%d",&s); addedge(n+1,s,0); } SPFA(n+1,n+1); if(dist[t]==INF) printf("-1\n"); else printf("%d\n",dist[t]); } return 0;}
hdu2680 Choose the best route 最短路（多源转单源）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。