[UVA] 318 - Domino Effect

題目連結

題意：

給你n個點和m條邊，點和點之間有骨牌，

會給你兩個點之間的骨牌個數，

問從點1開始推，一直到最後一個骨牌倒下會經過多少個骨牌，

最後一個骨牌是在哪個點，或在哪兩個點之間。

--------------------------------------------------

我的作法：

Dijkstra(維基百科) 可以算出1到所有點的最短距離

假設dis[i] 為 1到 i 的最短時間，

一直到最後一個骨牌的總時間 t = max(dis[i] + dis[j] + i到j的長度)/2，枚舉 i j

如果最後一個骨牌是在點上，那 t 就會是 dis[i]，否則就是在邊上。

--------------------------------------------------

程式碼：

/* 題目: UVa 318 - Domino Effect

 * Language: C++

 * Created on: 2015年12月21日

 *   Author: hanting

 */

#include <iostream>

#include <vector>

#include <iomanip> // setprecision

#include <queue> // priority_queue

using namespace std;

#define inf 0x3fffffff

struct Node

{

     int id, length;

     Node(int a, int b) :

                id(a), length(b)

     {

     }

     bool operator <(const Node& b) const

     {

           return length > b.length;

     }

};

vector<vector<Node> > adj;

vector<int> visit;

vector<int> dis;

vector<int> ans;

void init(int n)

{

     adj.assign(n, vector<Node>());

     visit.assign(n, 0);

     dis.assign(n, inf);

     ans.clear();

     ans.push_back(1);

}

void link(int a, int b, int l)

{

     adj[a].push_back(Node(b, l));

     adj[b].push_back(Node(a, l));

}

void Dijkstra()

{

     priority_queue<Node> que;

     que.push(Node(1, 0)); // start from node 1

     int curDis = 0;

     dis[1] = 0;

     while (que.size())

     {

           int cur = que.top().id;

           que.pop();

           visit[cur] = 1;

           for (int i = 0; i < adj[cur].size(); i++)

           {

                Node tmp = adj[cur][i];

                dis[tmp.id] = min(dis[tmp.id], dis[cur] + tmp.length);

                if (!visit[tmp.id])

                {

                     que.push(Node(tmp.id, dis[tmp.id]));

                }

           }

     }

}

void checkTheLast(double &maxi)

{

     for (int i = 1; i < adj.size(); i++)

     {

           for (int j = 0; j < adj[i].size(); j++)

           {

                int connect = adj[i][j].id;

                double tmp = (dis[i] + dis[connect] + adj[i][j].length) / 2.;

                if (tmp > maxi)

                {

                     maxi = tmp;

                     if (tmp == dis[i] or tmp == dis[connect])

                     {

                           ans.clear();

                           ans.push_back(tmp == dis[i] ? i : connect);

                     }

                     else

                     {

                           ans.clear();

                           ans.push_back(i);

                           ans.push_back(connect);

                     }

                }

           }

     }

}

int main()

{

     int nodeN, edgeN;

     int testCase = 1;

     while (cin >> nodeN >> edgeN and nodeN + edgeN)

     {

           init(nodeN + 1);

           for (int i = 0; i < edgeN; i++)

           {

                int node1, node2, len;

                cin >> node1 >> node2 >> len;

                link(node1, node2, len);

           }

           Dijkstra();

           double maxi = 0;

           checkTheLast(maxi);

           cout << "System #" << testCase++ << endl;

           cout << fixed << setprecision(1);

           if (ans.size() < 2)

           {

                cout << "The last domino falls after " << maxi

                           << " seconds, at key domino " << ans[0] << "." << endl;

           }

           else

           {

                cout << "The last domino falls after " << maxi

                           << " seconds, between key dominoes " << ans[0] << " and "

                           << ans[1] << "." << endl;

           }

           cout << endl;

     }

     return 0;

}

 ----- ----- ----- ----- ----- ----- ----- ----- ----- -----

測資：

input

100 10

1 39 7218

1 88 783

1 92 8460

88 21 3278

39 87 744

39 88 1063

39 82 4476

87 1 4219

87 35 4504

35 15 2508

0 0

output

The last domino falls after 9602.0 seconds, at key domino 15.