2016年5月19日 星期四

UVA 11635 Hotel booking

/*
    題目連結

    最短路的變化題
    比起Dijkstra 我更喜歡SPFA
    雖然大家兩種都應該要會就是

    這題我們要建兩張圖
    一張是題目給的 邊記說在兩點間
    通行需要幾分鐘
    另一張圖是我們後來自己建的
    兩間飯店間有長度為一的邊 若且唯若
    兩者間能在一天內到達

    為了得到這第二張圖的邊
    我們先在第一張圖上 對每一個飯店
    做單源最短路 把所有距離 <= 600的飯店
    在第二張圖上加邊

    接著我們在第二張圖上
    以1為起點做最短路 看到點n的距離
    把距離減一 便是答案

    要注意說 我們把點1,n
    也視為飯店 因為我們也會在那邊停留
    這樣處理起來會比較方便
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int INF = 2e9;

int n, h;
bool hotel[10001];

struct E
{
    int to, dis;
    E(int _to, int _dis):to(_to),dis(_dis){}
};

vector<E> v[2][10001];

int dis[10001];
bool in[10001];

void SPFA(int s, vector<E> *v)
{
    fill(dis+1, dis+n+1, INF);
    fill(in+1, in+n+1, false);

    queue<int> que;

    dis[s] = 0;
    que.push(s);
    in[s] = true;

    while( !que.empty() )
    {
        int x = que.front();
        que.pop(), in[x] = false;

        for(int vi = 0; vi < v[x].size(); vi++)
        {
            int _to = v[x][vi].to, _dis = v[x][vi].dis;

            if( dis[_to] > dis[x]+_dis )
            {
                dis[_to] = dis[x]+_dis;

                if( !in[_to] )
                {
                    que.push(_to);
                    in[_to] = true;
                }
            }
        }
    }
}

int main()
{
    while(1)
    {
        scanf("%d", &n);
        if( !n ) break;

        fill(hotel+1, hotel+n+1, false);

        for(int i = 0; i < 2; i++)
            for(int ni = 1; ni <= n; ni++)
                v[i][ni].clear();

        scanf("%d", &h);

        for(int hi = 0; hi < h; hi++)
        {
            int c;
            scanf("%d", &c);
            hotel[c] = true;
        }

        hotel[1] = hotel[n] = true;

        int m;
        scanf("%d", &m);

        for(int mi = 0; mi < m; mi++)
        {
            int a, b, t;
            scanf("%d %d %d", &a, &b, &t);

            v[0][a].emplace_back(b, t);
            v[0][b].emplace_back(a, t);
        }

        for(int ni = 1; ni <= n; ni++)
            if( hotel[ni] )
            {
                SPFA(ni, v[0]);

                for(int nj = 1; nj <= n; nj++)
                    if( dis[nj] <= 600 && hotel[nj] )
                        v[1][ni].emplace_back(nj, 1);
            }

        SPFA(1, v[1]);

        if( dis[n] == INF ) puts("-1");
        else printf("%d\n", dis[n]-1);
    }
}

沒有留言:

張貼留言