题意：从1派学生到2-n这n-1个点 求去并且回来的最短路 就是1到各点的最短路之和和各点到1的最短路之和 给的是有向图
思路：对于1到各个点的最短路直接Dijkstra求出无压力 然后各个点到1的最短路可以反向建图后再求一次从1到各个点的最短路
对于很多点到一个点的情况可以考虑反向建图 转变成单源最短路
#include#include #include #include 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 edges; vector 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 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; }