首页 > 代码库 > hdu 2066 一个人的旅行(裸dijkstra)
hdu 2066 一个人的旅行(裸dijkstra)
http://acm.hdu.edu.cn/showproblem.php?pid=2066
求多源多汇的最短路,n最大为1000,floyd三重循环会超时。继续dijkstra吧。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1100; int Map[maxn][maxn]; int t,s,d; int ss[maxn],dd[maxn]; int n; int dis[maxn]; int vis[maxn]; void dijkstra(int src) { memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); vis[src] = 1; for(int i = 1; i <= n; i++) dis[i] = Map[src][i]; dis[src] = 0; for(int i = 1; i <= n; i++) { int Min = INF,pos; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < Min) { Min = dis[j]; pos = j; } } vis[pos] = 1; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] > dis[pos] + Map[pos][j]) dis[j] = dis[pos] + Map[pos][j]; } } } int main() { while(~scanf("%d %d %d",&t,&s,&d)) { n = -1; memset(Map,INF,sizeof(Map)); int u,v,w; for(int i = 0; i < t; i++) { scanf("%d %d %d",&u,&v,&w); if(Map[u][v] > w) Map[u][v] = Map[v][u] = w; n = max( max(u,v),n ); } for(int i = 0; i < s; i++) scanf("%d",&ss[i]); for(int i = 0; i < d; i++) scanf("%d",&dd[i]); for(int i = 1; i <= n; i++) Map[i][i] = 0; int ans = INF; for(int i = 0; i < s; i++) { dijkstra(ss[i]); for(int j = 0; j < d; j++) ans = min(ans,dis[dd[j]]); } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。