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;  
}