[UVA] 10801 - Lift Hopping

題目連結

我的做法：
0到k最短路徑問題，priority_queue實做Dijkstra演算法。

==================================================
程式碼：
/* 題目: UVa 10801 - Lift Hopping
 * Language: C++
 * Created on: 2016年12月14日
 *   Author: hanting
 */
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
using namespace std;
struct Node
{
    int num, dis;
    Node(int _num = 0, int _dis = 0)
    {
        num = _num;
        dis = _dis;
    }
    bool operator() (const Node &node1, const Node &node2)const
    {
        return node1.dis < node2.dis;
    }
};
class Graph
{
private:
    vector<vector<Node> > adj;
public:
    int Dijkstra(int s, int t)
    {
        vector<int> dis(adj.size());
        for(int i = 0; i < adj.size(); i++)
        {
            dis[i] = 0x3fffffff;
        }
        dis[s] = 0;
        priority_queue<Node, vector<Node>, Node > pque;
        pque.push(Node(s, 0));
        while(pque.size())
        {
            int cur = pque.top().num;
            pque.pop();
            for(int i = 0; i < adj[cur].size(); i++)
            {
                Node next = adj[cur][i];
                int u = cur,
                    v = next.num,
                    w = next.dis;
                if(dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    pque.push(Node(v, dis[v]));
                }
            }
        }
        return dis[t];
    }
    void initNodeN(int nodeN)
    {
        adj.assign(nodeN, vector<Node>());
    }
    void link(int s, int t, int w = 0)
    {
        if(s % 100 == 0) s = 0;
        adj[s].push_back(Node(t, w));2
        adj[t].push_back(Node(s, w));
    }
};
int main()
{
    int elevatorN, k;
    while(cin >> elevatorN >> k)
    {
        vector<int> weight(elevatorN);
        for(int i = 0; i < elevatorN; i++)
        {
            cin >> weight[i];
        }
        Graph graph;
        graph.initNodeN(100*elevatorN);
        cin.get();
        map<int, int> Map;
        for(int i = 0; i < elevatorN; i++)
        {
            string str;
            getline(cin ,str);
            stringstream sin(str);
            int s, t;
            sin >> s;
            Map[100*i+s] = 1;
            for(int j = 100*i+s-100; j >= 0; j -= 100)
            {
                if(Map[j])
                {
                    graph.link(100*i+s, j, 60);
                }
            }
            while(sin >> t)
            {
                graph.link(100*i+s, 100*i+t, (t-s)*weight[i]);
                Map[100*i+t] = 1;
                for(int j = 100*i+t-100; j >= 0; j -= 100)
                {
                    if(Map[j])
                    {
                        graph.link(100*i+t, j, 60);
                    }
                }
                s = t;
            }
        }

        int mini = graph.Dijkstra(0, k);
        for(int i = 1; i < elevatorN; i++)
        {
            mini = min(mini, graph.Dijkstra(0, k+100*i));
        }
        if(mini == 0x3fffffff) cout << "IMPOSSIBLE" << endl;
        else cout << mini << endl;
    }
    return 0;
}