http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1509
如果TIOJ又掛了的話= =
http://zerosea.tfcis.org:8080/JudgeOnline/showproblem?problem_id=1128
做第一次dijkstra -> 把邊反過來 -> 再做一次
P.S. 冏我都被J睿捏好玩的 不捏我都想不到…
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#define INF 1000000001
using namespace std;
typedef struct {
int to;
int cost;
} edge;
typedef pair<int, int> P;
vector<edge> G[1000001];
vector<edge> R[1000001];
long long d[1000001];
bool visited[1000001];
priority_queue<P, vector<P>, greater<P> > que;
int main()
{
int s, t, c, V, E;
long long sum;
while (~scanf("%d%d", &V, &E)) {
sum = 0;
fill(d, d + V + 1, INF);
memset(visited, false, sizeof(visited));
edge e;
for (int i = 1; i <= V; i++) {
G[i].clear();
R[i].clear();
}
for (int i = 0; i < E; i++) {
scanf("%d%d%d", &s, &t, &c);
e.to = t;
e.cost = c;
G[s].push_back(e);
e.to = s;
R[t].push_back(e);
}
d[1] = 0;
que.push(P(0, 1));
while (que.size()) {
P p;
while (que.size()) {
p = que.top();
que.pop();
if (!visited[p.second]) {
break;
}
}
visited[p.second] = true;
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (int i = 0; i < G[v].size(); i++) {
edge e = G[v][i];
if (d[v] + e.cost < d[e.to]) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
bool jump = false;
for (int i = 1; i <= V; i++) {
if (d[i] == INF) {
jump = true;
break;
}
sum += d[i];
}
if (jump) {
puts("0");
continue;
}
que.push(P(0, 1));
fill(d, d + V + 1, INF);
memset(visited, false, sizeof(visited));
d[1] = 0;
while (que.size()) {
P p;
while (que.size()) {
p = que.top();
que.pop();
if (!visited[p.second]) {
break;
}
}
visited[p.second] = true;
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (int i = 0; i < R[v].size(); i++) {
edge e = R[v][i];
if (d[v] + e.cost < d[e.to]) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
for (int i = 1; i <= V; i++) {
if (d[i] == INF) {
jump = true;
break;
}
sum += d[i];
}
if (jump) {
puts("0");
continue;
}
printf("%I64d\n", sum);
}
return 0;
}