P1629 邮递员送信

邮递员送信

---

• 每次送一次都要回去拿，去的最短路和回来的最短路
• 给的边是有向边
• 源点到其他点最短路之和
• 其他点到源点的最短路之和（相当于反向建图源点到其他点最短路之和）

---

代码

#include <bits/stdc++.h>

#define pr pair<int, int>
#define mk make_pair

using namespace std;

const int N = 1e5 + 1;

struct Edge_{
	int u,v,w;
}edge_[N << 2];

struct Edge{
	int v,w,nxt;
}edge[N << 2];

int n,m,top,cost;
int head[N],dist[N];

void addedge(int u, int v, int w){
	edge[++top].v = v;
	edge[top].w = w;
	edge[top].nxt = head[u];
	head[u] = top;
}

priority_queue<pr, vector<pr>, greater<pr> > q;
void Dijkstra(){
	for(int i = 1; i <= n; ++i) dist[i] = 0x7fffffff;
	dist[1] = 0;
	q.push(mk(dist[1], 1));
	while(!q.empty()){
		int u = q.top().second;
		int d = q.top().first; q.pop();
		if(d > dist[u]) continue;			
		for(int i = head[u]; i; i = edge[i].nxt){
			int v = edge[i].v;
			int w = edge[i].w;
			if(dist[u] + w < dist[v]) dist[v] = dist[u] + w, q.push(mk(dist[v], v));
		}
	}
	for(int i = 2; i <= n; ++i) cost += dist[i];
}
		

int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) cin >> edge_[i].u >> edge_[i].v >> edge_[i].w;
	for(int i = 1; i <= m; ++i) addedge(edge_[i].u, edge_[i].v, edge_[i].w);
	Dijkstra(); top = 0; for(int i = 1; i <= n; ++i) head[i] = 0;
	for(int i = 1; i <= m; ++i) addedge(edge_[i].v, edge_[i].u, edge_[i].w);
	Dijkstra(); top = 0;
	cout << cost;
	return 0;
}