Wednesday, March 7, 2012

[code] TIOJ-1509 地道問題 (TOI初選2008pD)

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

No comments:

Post a Comment