解題區/解題區 - UVa

UVa 12717 - Fiasco

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Natasha always mixes up things in her algorithm classes. Last week Prof. Chhaya Murthy gave the class a classical problem -finding shortest path to all nodes from a special node of a weighted graph. Before that in another class, the professor taught them Prim’s and Dijkstra’s algorithms which are similar looking but does very different things. Always confused, poor Natasha submitted something
very similar to the Prim’s algorithm (actually we should call it Natasha’s lgorithm), she didn’t test it properly. Pseudocode of her algorithm looks as follows

uva 12717

After submission, she showed the code to a friend who is good at algorithms. That friend immediately found the aw. Natasha was really terrifed and started to cry. Then there came the guys, the guys who liked her. They jumped at the opportunity and got hold of the dataset to be used to test the solutions. Your friend Rehan is one of those guys. He really wanted to impress Natasha. He asked you to change the dataset in such a way that Natasha’s algorithm gives the right result. After the change, Rehan will somehow be able to put the modified data with the old timestamp. Rehan told you that:

  1. The dataset has T test cases.
  2. Each case contains a connected weighted undirected graph with n nodes and
    m edges.
  3. Each case will contain a source node source.
  4. Edge weights are positive and distinct.

To avoid suspicion, Rehan asked you not to change which vertices the edges connect, or the overall set of edge weights. You may only reorder which weights are assigned to which edges

Input

The first line of the input denotes the number of datasets T (1 < T <= 15). T sets of case will follow. Each case will start with a triplet of numbers n (2 <= n <= 2500), m (1 <= m <= 25000) and source (1 <= source <= n) | the number of nodes, the number of edges and the starting node respectively.

Each of the next m lines will contain a triplet of numbers (u, v, w) meaning that there is an edge between node u and node v with weight w (1 <= w <= m). Nodes are numbered from 1 to n.

It is guaranteed that there is no duplicate or self-edges in the input and the graph is connected. In each given graph, all edge weights will be distinct.

Output

For each set of input, print one set of output. First line of a set should be of the format, Case X: where X is the case number. Then print each edge triplet | one triplet (u, v, w) in each line separated by a single space. The edges should be printed in the order given in the input. If there is more than one solution to a dataset, any one of them will do.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3

Sample Output

1
2
3
4
5
6
7
8
9
10
Case 1:
2 4 7
1 4 9
7 2 3
3 4 8
5 7 1
7 3 4
6 1 5
6 3 6
5 6 2

Solution

題目描述：
// 給一個錯誤代碼，修改測資，使錯誤代碼輸出正確。
在一門演算法課程中，上到了最短路徑算法，教授指出了 Prim 和 Dijkstra 算法之間的不同，課堂上有個妹子很不小心搞混了這兩個算法，甚至弄出了更奇怪的程序，這代碼其中有缺陷，她和朋友分享代碼後，沒想到朋友瞬間戳出輸出錯誤的測資，妹子一時之間哭了出來。

現在為了擄獲芳心，請修改測資，使得錯誤代碼有一樣的正確輸出。

題目解法：
這個妹子錯的地方在於，更新的時候，沒有將為探訪點的情況加以考慮，直接以 BFS 的方式丟入，那麼在隨後更新的路徑長就不會被丟入 Priority Queue，這樣在 Dijkstra 的更新順序上就會出錯。也就是說，只要 Graph 的權重依據 BFS 順序 符合由小到大，不會出現隨後更新的問題即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int> g[2505];
int used[25005];
int in_x[25005], in_y[25005], in_w[25005];
map< pair<int, int>, int> shortest_tree;
void bfs(int source) {
    queue<int> 	Q;
    int 		u, v, e = 0;
    Q.push(source), used[source] = 1;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(used[v])	continue;
            used[v] = 1;
            shortest_tree[make_pair(u, v)] = in_w[e], e++;
            Q.push(v);
        }
    }
}
int main() {
    int testcase, cases = 0;
    int n, m, source;
    int x, y, w;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &m, &source);
        
        for(int i = 1; i <= n; i++) {
            g[i].clear();
            used[i] = 0;
        }
        shortest_tree.clear();
        
        for(int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(y);
            g[y].push_back(x);
            in_x[i] = x, in_y[i] = y, in_w[i] = w;
        }
        
        for(int i = 1; i <= n; i++)
            sort(g[i].begin(), g[i].end());
        sort(in_w, in_w + m);
        bfs(source);
        
        printf("Case %d:\n", ++cases);
        map< pair<int, int>, int>::iterator it, jt, kt;
        int e = m - 1;
        kt = shortest_tree.end();
        for(int i = 0; i < m; i++) {
            it = shortest_tree.find(make_pair(in_x[i], in_y[i]));
            jt = shortest_tree.find(make_pair(in_y[i], in_x[i]));
            if(it != kt)
                w = it->second;
            else if(jt != kt)
                w = jt->second;
            else
                w = in_w[e], e--;
            printf("%d %d %d\n", in_x[i], in_y[i], w);
        }
    }
    return 0;
}
/*
1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3
*/