HDU 2066 最短路

本文主要是介绍HDU 2066 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*这个题目只要看成是草儿所在的城市到各点的单源最短路径就可以了所以把草儿所在的城市标记为0但要注意的是和草儿邻近的城市不需要坐火车的，所以花费的时间为0只要用Dijkstra算法就可以了
*/
#include<iostream>
using namespace std;
const int maxn = 1000000;
int f[1002][1002], ct[1002], wt[1002], dis[1002];
bool vis[1002];
int t, s, d, n;void dij()
{for(int i = 0; i <= n; i++)dis[i] = f[0][i];vis[0] = true;while(true){int Min = maxn, mj = -1;for(int i = 0; i <= n; i++)if(!vis[i] && dis[i]<Min) Min = dis[i], mj = i;if(mj==-1 || mj==n) break;vis[mj] = true;for(int i = 0; i <= n; i++)if(!vis[i] && dis[i]>dis[mj]+f[mj][i])dis[i] = dis[mj]+f[mj][i];}
}int main()
{while(cin >> t >> s >> d){n = -maxn;for(int i = 0; i < 1002; i++){dis[i] = maxn;vis[i] = false;for(int j = 1; j < 1002; j++)if(i != j) f[i][j] = f[j][i] = maxn;else f[i][j] = 0;}for(int i = 1; i <= t; i++){int a, b, c;cin >> a >> b >> c;if(a > n) n = a;if(b > n) n = b;//用来找到编号最大的城市if(f[a][b] > c)f[a][b] = f[b][a] = c;}for(int i = 1; i <= s; i++){cin >> ct[i];f[0][ct[i]] = f[ct[i]][0] = 0;//邻近城市花费时间为0}for(int i = 1; i <= d; i++)cin >> wt[i];dij();int Min = maxn;for(int i = 1; i <= s; i++)if(Min > dis[wt[i]]) Min = dis[wt[i]];//找到源点-到草儿想去城市中花费最少的时间cout << Min << endl;}return 0;
}

这篇关于HDU 2066 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---