HDU 1535 Invitation Cards 2次Dijkstra来回最短路

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

题目来源：HDU 1535 Invitation Cards

题意：从1派学生到2-n这n-1个点  求去并且回来的最短路 就是1到各点的最短路之和和各点到1的最短路之和 给的是有向图

思路：对于1到各个点的最短路直接Dijkstra求出无压力 然后各个点到1的最短路可以反向建图后再求一次从1到各个点的最短路

对于很多点到一个点的情况可以考虑反向建图 转变成单源最短路

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1000010;
struct edge
{int u, v, w;
};
struct HeapNode
{int u, d;bool operator < (const HeapNode& rhs)const{return d > rhs.d;}
};
vector <edge> edges;
vector <edge> G[maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
void Dijkstra()
{//for(int i = 0; i <= n; i++)//	dis[i] = 9999999999;memset(dis, 0x7f, sizeof(dis));dis[1] = 0;memset(vis, false, sizeof(vis));priority_queue <HeapNode> Q;Q.push((HeapNode){1, 0});while(!Q.empty()){HeapNode x = Q.top();Q.pop();int u = x.u;if(vis[u])continue;vis[u] = true;for(int i = 0; i < G[u].size(); i++){edge e = G[u][i];int v = e.v;if(dis[v] > x.d + e.w){dis[v] = x.d + e.w;Q.push((HeapNode){v, dis[v]});	}}}
}
int main()
{int T;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);edges.clear();for(int i = 0; i < m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);edges.push_back((edge){u, v, w});}int ans = 0;for(int i = 0; i <= n; i++)G[i].clear();for(int i = 0; i < m; i++){edge e = edges[i];G[e.u].push_back((edge){e.u, e.v, e.w});}Dijkstra();for(int i = 2; i <= n; i++)ans += dis[i];for(int i = 0; i <= n; i++)G[i].clear();for(int i = 0; i < m; i++){edge e = edges[i];G[e.v].push_back((edge){e.v, e.u, e.w});}Dijkstra();for(int i = 2; i <= n; i++)ans += dis[i];printf("%d\n", ans);}return 0;
}

 

这篇关于HDU 1535 Invitation Cards 2次Dijkstra来回最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---