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;}

这篇关于hdu 2066 一个人的旅行(裸dijkstra)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---