2015年9月9日 星期三

2015/09/09 Codeforces 575G. Run for beer

/*
    很有趣的一道最短路

    基本上最短路
    我們在每個點都是要紀錄距離的
    但是這題有一個性質
    就是 你從哪個點來比較重要
    所以只要記錄說 你是從第幾遠的點來的、
    你過來的邊多長 和 你走了幾條邊就好

    我們從點N-1往回做最短路
    接著再想辦法 還原出我們走的路徑
*/
// http://codeforces.com/problemset/problem/575/G
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int d[200000]; int clk = 0;

bool visit[200000];
int fa[200000];
int cost[200000];

struct e
{
    int t, c;
    e(int _t, int _c){ t = _t; c = _c; }
};

struct s:e
{
    int f, cnt;
    s(int _f, int _t, int _c, int _cnt):e(_t, _c){ f = _f; cnt = _cnt; }

    bool operator<(const s &p)const
    {
        return d[f] > d[p.f] ||
        d[f] == d[p.f] && c > p.c ||
        d[f] == d[p.f] && c == p.c && cnt > p.cnt;
    }

    bool operator==(const s &p)const
    { return d[f] == d[p.f] && c == p.c; }

};

priority_queue<s> pri;
vector<e> v[200000];

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

    for(int Mi = 0; Mi < M; Mi++)
    {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);

        v[a].push_back(e(b, l) );
        v[b].push_back(e(a, l) );
    }

    s past = s(N-1, N-1, 0, 0);
    pri.push(s(N-1, N-1, 0, 0) );

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

        int f, t, c, cnt;
        f = p.f; t = p.t;
        c = p.c; cnt = p.cnt;

        if( visit[t] ) continue;
        visit[t] = true;
        fa[t] = f;
        cost[t] = c;

        if( p == past ) d[t] = clk;
        else d[t] = ++clk;
        past = p;

        for(int vi = 0; vi < v[t].size(); vi++)
            if( !visit[v[t][vi].t ] )
                pri.push(s(t, v[t][vi].t, v[t][vi].c, cnt+1) );
    }

    vector<int> p, q;
    int t = 0;

    q.push_back(0);
    while( t != N-1 )
    {
        p.push_back(cost[t] );
        q.push_back(fa[t] );
        t = fa[t];
    }

    bool flag = false;

    for(int pi = p.size()-1; pi >= 0; pi--)
    {
        if( !flag && !p[pi] && pi ) continue;
        else{ printf("%d", p[pi]); flag = true; }

        if( pi == 0 ) puts("");
    }

    printf("%d\n", q.size());

    for(int qi = 0; qi < q.size(); qi++)
    {
        printf("%d", q[qi]);

        if( qi != q.size()-1 ) printf(" ");
        else puts("");
    }
}

沒有留言:

張貼留言