洛谷 P1629 邮递员送信

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;

const int N = 1e3 + 10;

int n, m, dis[N];
bool vis[N];
vector<pair<int, int> > G[N];
vector<pair<int, int> > Gf[N];

void spfa() {
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	vis[1] = true;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = 0; i < G[u].size(); ++i) {
			int v = G[u][i].first;
			int w = G[u][i].second;
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				if (vis[v] == 0) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
void spfa2() {
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	vis[1] = true;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = 0; i < Gf[u].size(); ++i) {
			int v = Gf[u][i].first;
			int w = Gf[u][i].second;
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				if (vis[v] == 0) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}


int main() {
	cin >> n >> m;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back(make_pair(v, w));
		Gf[v].push_back(make_pair(u, w));
	}
	spfa();
	int res = 0;
	for (int i = 1; i <= n; ++i) res += dis[i];
	spfa2();
	for (int i = 1; i <= n; ++i) res += dis[i];
	cout << res;
    return 0;
}