2016年9月11日 星期日

2010-2011 ACM-ICPC, NEERC, Moscow Subregional Contest D. Distance

/*
    題目連結不知道怎麼附上
    所以就稍微口述一下吧

    題目:
    你有 N <= 100000 個點
    有的點對之間會有帶正權的邊
    然後其中又有一些點 會是特殊點
    問你距離最近的特殊點對 彼此的距離距離為何?

    題解:
    這一題 一看就會聯想到最短路
    一開始隊友想到一個錯的做法
    對所有特殊點 同時開始做 Dijkstra
    直到pop 出來的點是特殊點就結束
    這其實有保證正確性 但複雜度是爛的
    只是特殊點 彼此距離很遠
    而離非特殊點們很近 就會炸開變成 O(VE*logV)

    不過這確實給了一點靈感
    最後我想想這其實就是 多起點的最短路/次短路
    (雖然說多了一點限制 比方說兩條路不能來自於同一點)
    然後 答案就會是 所有點的 最短路+次短路 當中值最小的
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> e;
#define t first
#define d second

typedef long long ll;

bool hv[100001];
int S[100001];

vector<e> v[100001];

ll ans = 2e18;
ll dis[100001]; int fa[100001]; int cnt[100001];

struct s{
    int f, t, d;
    s(int _a, int _b, int _c):f(_a), t(_b), d(_c){}

    bool operator<(const s &p)const{
        return d > p.d;
    }
};

priority_queue<s> pri;

int main()
{
    int N, K, L;
    scanf("%d %d %d", &N, &K, &L);

    for (int Ni = 0; Ni < N; Ni++) {
        int x;
        scanf("%d", &x);
        S[Ni] = x;

        if ( hv[x] ) {
            puts("0");
            return 0;
        } else hv[x] = true;
    }

    for (int Ki = 1; Ki <= K; Ki++)
        dis[Ki] = 2e18;

    for (int Li = 0; Li < L; Li++) {
        int b, c, d;
        scanf("%d %d %d", &b, &c, &d);

        v[b].emplace_back(c, d);
        v[c].emplace_back(b, d);
    }

    for (int Ni = 0; Ni < N; Ni++)
        pri.emplace(S[Ni], S[Ni], 0);

    while ( !pri.empty() ) {
        s p = pri.top();
        pri.pop();

        int t = p.t, f = p.f, d = p.d;

        if ( f != t && f != fa[t] ) ans = min(ans, dis[t]+p.d);

        if ( fa[t] == f ) continue;

        if ( cnt[t] < 2 ) {

            if ( fa[t] == 0 ) {
                fa[t] = f;
                dis[t] = d;
            }

            for (auto x : v[t]) {
                pri.emplace(f, x.t, d+x.d);
            }

            cnt[t]++;
        }
    }

    printf("%lld\n", ans*3);
}

沒有留言:

張貼留言