TRAFFICN - Traffic Network

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
const int N = 10005;
const int oo = 1000000009;
using namespace std;
vector<ii> a[2][N];
int d[2][N], m, n, s, tt, k, t;

void Dijkstra(int source, int p) {
    priority_queue<ii, vector<ii>, greater<ii> > Q;
    Q.push(ii(0, source));
    int i, v, uv, u, du;
    ii t;
    for(i=1; i<=n; i++) d[p][i] = oo;
    d[p][source] = 0;
    while (Q.size()) {
        t = Q.top(); Q.pop();
        u = t.second; du = t.first;
        if (du != d[p][u]) continue;
        for(i=0; i<a[p][u].size(); i++) {
            v = a[p][u][i].first;
            uv = a[p][u][i].second;
            if (d[p][v] > d[p][u] + uv) {
                d[p][v] = d[p][u] + uv;
                Q.push(ii(d[p][v], v));
            }
        }
    }
}

int main()
{
    //freopen("TRAFFICN.in", "r", stdin);
    scanf("%d\n", &tt);
    int i, u, v, c, res;
    while (tt--) {
        scanf("%d %d %d %d %d\n", &n, &m, &k, &s, &t);
        for(i=1; i<=n; i++) {a[0][i].clear();a[1][i].clear();}
        for(i=1; i<=m; i++) {
            scanf("%d %d %d\n", &u, &v, &c);
            a[0][u].push_back(ii(v, c));
            a[1][v].push_back(ii(u, c));
        }
        Dijkstra(s, 0);
        Dijkstra(t, 1);
        res = d[0][t];
        while (k--) {
            scanf("%d %d %d\n", &u, &v, &c);
            res = min(res, min(d[0][u] + c + d[1][v], d[0][v] + c+ d[1][u]));
        }
        if (res == oo) res = -1;
        printf("%d\n", res);
    }
    return 0;
}

Download