acm/172.cpp at master · xdd44-utopia/acm · GitHub

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

#define LL 2147483647;

using namespace std;

struct Node {
	int cnt;
	bool visit1;
	bool visit2;
	int dist1;
	int dist2;
	vector<int> edges;
	vector<int> dist;

	void clear() {
		cnt = 0;
		visit1 = false;
		visit2 = false;
		dist1 = LL;
		dist2 = LL;
		edges.clear();
		dist.clear();
	}
};

Node juns[1000];

class Compare1 {
public:
	bool operator() (int i, int j) {
		return juns[i].dist1 > juns[j].dist1;
	}
};
class Compare2 {
public:
	bool operator() (int i, int j){
		return juns[i].dist2 > juns[j].dist2;
	}
};

int main() {

	//freopen("/Users/xdd44/Documents/Code/172/sample.in", "r", stdin);

	int n,m;
	int caseNum = 0;
	while (cin >> n >> m) {
		caseNum++;
		for (int i=0;i<n;i++) {
			juns[i].clear();
		}

		for (int i=0;i<m;i++) {
			int t1, t2, t3;
			cin >> t1 >> t2 >> t3;
			juns[t1].cnt++;
			juns[t1].edges.push_back(t2);
			juns[t1].dist.push_back(t3);
			juns[t2].cnt++;
			juns[t2].edges.push_back(t1);
			juns[t2].dist.push_back(t3);
		}

		priority_queue< int, vector<int>, Compare1 > q1;
		priority_queue< int, vector<int>, Compare2 > q2;
		juns[0].dist2 = 0;
		q2.push(0);
		bool isUpdated = false;
		do {
			isUpdated = false;
			if (!q1.empty()) {
				isUpdated = true;
				int cur = q1.top();
				q1.pop();
				juns[cur].visit1 = true;
				for (int i=0;i<juns[cur].cnt;i++) {
					int pointer = juns[cur].edges[i];
					if (!juns[pointer].visit2 && juns[pointer].dist2 > juns[cur].dist1 + juns[cur].dist[i]) {
						juns[pointer].dist2 = juns[cur].dist1 + juns[cur].dist[i];
						q2.push(pointer);
					}
				}
			}
			if (!q2.empty()) {
				isUpdated = true;
				int cur = q2.top();
				q2.pop();
				juns[cur].visit2 = true;
				for (int i=0;i<juns[cur].cnt;i++) {
					int pointer = juns[cur].edges[i];
					if (!juns[pointer].visit1 && juns[pointer].dist1 > juns[cur].dist2 + juns[cur].dist[i]) {
						juns[pointer].dist1 = juns[cur].dist2 + juns[cur].dist[i];
						q1.push(pointer);
					}
				}
			}
		} while (isUpdated);

		cout << "Set #" << caseNum << endl;
		if (juns[n-1].dist2 < 2147483647) {
			cout << juns[n-1].dist2 << endl;
		}
		else {
			cout << "?\n";
		}
	}

	return 0;
}