解題區►出題解題

[ACM 題目] 河道分界

Problem

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

Input

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

Output

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

Sample Output

1
2
3
4
5
6
[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

More

sample

Solution

1
Read More +
解題區►出題解題

[ACM 題目] 樹形鎖頭

Problem

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

Input

輸入有多組測資。

每一組測資第一行 會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

Output

每組測資輸出一行，分別將節點權重輸出。

Sample Input

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

Sample Output

1
5 3 5 3 2 4 8

Solution

1
Read More +
學校課程►通識課程

[通識] 文明的進程 Week 2

Front of the Class

電影《Front of the Class》(中譯：叫我第一名)，是一部關於妥瑞症的一部電影。

問題

  • 男主角不想在什麼地點出現？這些地點有什麼共同特徵？

電影院、教會、音樂會、圖書館、體育場 … 等，這幾個地點都有著密集的人群，而且屬於室內環境，參與的人都有必須遵守的共同禮儀，因此無法容忍偶發性不正常的反應，這將會造成秩序上的不平衡。

  • 為什麼面試教師一直遭校方的反對？

首先，猜測幾點，先不管妥瑞症是否會對於男主角教學能力上的影響，既然捧著校方認可的同意書和成績，面試的基本門檻是過了。但是，哪個地方都不想要找一般的教師呢？一個突然會狗叫的教師將會給學校的門面帶來多少影響？是不是會有家長不讓學生進這個學校？即使校長願意讓男主在此教書，而家長的無知是否又會造成招生困難？

因此，害怕成為異類的校方，當然不想立刻收這位老師進來，不管後面的利益為何，有時候根本屬於未知的情況，因為根本沒有這種先例存在的話，只有極少數的人敢願意嘗試。

「害怕」和「不想」兩回事

  • 如果身邊有一個反應不太正常的人，你會怎麼做？

當然，妥瑞症所造成的肢體痙攣看來的確有點可怕，但是並非看起來就是鬼鬼祟祟、心術不正的長相，要恰好湊出這個組合的面貌，對於妥瑞症來說還真有點難度。反應不太正常的人其實也沒有好擔心的，高中同學也是常常在教室放屁，他自己也說忍不住，甚至有一天他特地跑到教室外面放屁，結果全部午睡的教室同學，全都被屁聲驚醒起來為他拍手叫好。

這麼三年過去，屁聲也是家常便飯了，想起來是相當特別，但誰沒有那麼一兩點特別之處呢？只是恰好沒有反應在外觀行為上！

而我，其實常常聽不懂別人說的任何一個詞，不管是中文還是英文，若沒有演講者般的口說，單純靠預測和推理得到「現在說了什麼」其實相當辛苦！有時候往往是無法預測，當沒有跟說話者很熟的時候。我姊也是因為這樣，常常把我抓去找耳科看有沒有耳朵問題，還是聽力退化，但是聽力似乎還算正常。「 聽得到，卻聽不懂 」的痛苦，一定會有人說是沒專心聽，請問「誰願意聽不清楚」，一堆人寧可聽不到一些雜語呢！

想到要跟人對談，就要有失敗的覺悟，拜託別人講第二次的勇氣越磨越光。

即使中文影片，有時還真希望有字幕 …

Read More +
手札日記

影響我最深的十本書

文

上星期五六去台中一趟，也算是開學前的最後一趟玩樂。回程的路上，老妮可突然問我想一想 影響最深的十本書 ，這問題讓我在火車上困惑相當久。想說怎麼會突然問這問題，原來是有人模仿冰桶在點名玩這一套遊戲。嘛，肯定不會有人點我的。

至少目前過了快 48 小時，一點耳聞也沒有。

我討厭看書，說是影響最深的十本書

  1. 英漢辭典
  2. 英漢辭典
  3. 英漢辭典
  4. 英漢辭典
  5. 英漢辭典
  6. 英漢辭典
  7. 英漢辭典
  8. 英漢辭典
  9. 英漢辭典
  10. 英漢辭典

英漢辭典 真的很重要，所以要說十次！演算法、教科書、資訊相關書目 … 等，看過封面而沒讀盡，打開閱閱，沒讀完都是常態。這些書沒有讀完但仍然影響了我，教會了我放棄，於是就這麼颯爽地讀到一半了！既然偷偷跟我說叫我放棄，我就放下書來！能影響我的書到底在哪裡呢？

現在，剛得知畢業門檻只能考英文檢定，影響最深的絕對只有英漢辭典，可惜這個 小夥伴 一定會被在任何場所禁止、無用。真是給了人希望、也給了幻滅。

還記得動畫 《戰鬥司書》 ？如果人死的存在將成為一本書 … 那肯定是很有趣的世界，而我又能成為什麼樣的一本書呢。

影響我最深的到底是什麼書？以人構成的書嗎？看得動畫都比書多，該如何是好。

附錄

【點名－影響我最深的十本書】

1.《Introduction to Algorithms》，ISBN 0-262-03293-7，Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein，2nd ed，2001。
2.《Computational Complexity》，ISBN 0-201-53082-1，Papadimitriou, Christos，1st ed，Addison Wesley，1994。
3.《The Rise and Fall of the Great Powers: Economic Change and Military Conflict From 1500 to 2000》（《大國的興衰》、《大國崛起》），ISBN 0-394-54674-1，Paul Kennedy，1987。
4.《The complete Lojban language》，ISBN 0-9660283-0-9，John Woldemar Cowan。
5.《ヘタリア Axis Powers》（《義呆利 Axis Powers》），日丸屋秀和。
6.《百年流離》鴨子，2012。
7.《灼眼のシャナ》（《灼眼的夏娜》），高橋彌七郎。
8.《古詩十九首》
9.《詩經》
10.《算法艺术与信息学竞赛》，ISBN 978-7-302-07800-5，刘汝佳，清华大学出版社，2004。
11.《TIGER×DRAGON！》，竹宮ゆゆこ。
12.《中國文學史演義》，錢念孫，四版，2006。
13.《暗黑童話》，ISBN：978-9-866-95482-5，乙一，2007。

許胖大神
Read More +
解題區►解題區 - UVa

UVa 12792 - Shuffled Deck

Problem

給定一種洗牌方式，請問重複多少次之後會復原到原本一開始的排列。

Sample Input

1
2
3
4
4
6
2
100002

Sample Output

1
2
3
4
4
3
2
100002

Solution

一道置換群的題目，將置換的方式找出，接著找一組一組循環置換集合，找到最小公倍數即可。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[1<<21], used[1<<21] = {};
int testcase = 0;
long long gcd(long long x, long long y) {
	long long t;
	while (x%y)
		t = x, x = y, y = t%y;
	return y;
}
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		for (int i = 0; i < n; i++) {
			if (i&1)
				A[i] = i/2;
			else
				A[i] = i/2 + n/2;
		}
		
		testcase++;
		long long lcm = 1;
		for (int i = 0; i < n; i++) {
			if (A[i] != i && used[i] != testcase) {
				int ss = 0;
				for (int j = i; used[j] != testcase; j = A[j])
					used[j] = testcase, ss++;
				lcm = lcm / gcd(lcm, ss) * ss;
			}
		}
		printf("%d\n", lcm);
	}
	return 0;
}
/*
4
6
2
100002
*/
Read More +
解題區►解題區 - UVa

UVa 12797 - Letters

Problem

找一條最短路徑從左上到右下，並且中間經過的字母不會有同時大小寫出現，也就是說 A 和 a 不能同時出現、B 和 b 不能同時出現 …

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa

Sample Output

1
2
13
-1

Solution

窮舉可使用的字符，對於每一種限定方式進行 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int N, letter_cnt[128], letter_used[128];
int used[128][128] = {}, dist[128][128], testcase = 0, ret;
char g[128][128];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void dfs(int idx) {
	if (idx == 10) {
		queue<int> X, Y;
		int tx, ty, x, y;
		if (letter_used[g[0][0]] == 0)
			return;
		testcase++;
		X.push(0), Y.push(0);
		used[0][0] = testcase;
		dist[0][0] = 1;
		while (!X.empty()) {
			x = X.front(), X.pop();
			y = Y.front(), Y.pop();
			if (x == N-1 && y == N-1) {
				ret = min(ret, dist[x][y]);
				return;
			}
			for (int i = 0; i < 4; i++) {
				tx = x + dx[i], ty = y + dy[i];
				if (tx < 0 || ty < 0 || tx >= N || ty >= N)
					continue;
				if (used[tx][ty] == testcase || letter_used[g[tx][ty]] == 0)
					continue;
				used[tx][ty] = testcase;
				dist[tx][ty] = dist[x][y] + 1;
				X.push(tx), Y.push(ty);
			}
		}
		return ;
	}
	int c = 0;
	if (letter_cnt[idx + 'a']) {
		letter_used[idx + 'a'] = 1;
		dfs(idx+1);
		letter_used[idx + 'a'] = 0;
		c++;
	}
	if (letter_cnt[idx + 'A']) {
		letter_used[idx + 'A'] = 1;
		dfs(idx+1);
		letter_used[idx + 'A'] = 0;
		c++;
	}
	if (c == 0)
		dfs(idx+1);
}
int main() {
	while (scanf("%d", &N) == 1) {
		for (int i = 0; i < N; i++)
			scanf("%s", g[i]);
		memset(letter_cnt, 0, sizeof(letter_cnt));
		memset(letter_used, 0, sizeof(letter_used));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				letter_cnt[g[i][j]]++;
		ret = 0x3f3f3f3f;
		dfs(0);
		printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12791 - Lap

Problem

在賽車運動中，常用 Lap 表示套一圈賽道所消耗的時間，現在有多名賽車手，給予最快一圈多久、最慢一圈多久，請問在最快車手第幾圈的時候，可以倒追最慢的車手。

Sample Input

1
2
3
4
1 10
4 8
5 7
6875 7109

Sample Output

1
2
3
4
2
2
4
31

Solution

懶得推導公式，二分倒追的時間，找到何時會產生倒追，再計算第幾圈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h> 
#include <math.h>
int main() {
	int X, Y;
	while (scanf("%d %d", &X, &Y) == 2) {
		double l = 0, r = 1e+30, mid;
		int ret = 0;
#define eps 1e-8
		while (fabs(l - r) > eps) {
			mid = (l + r)/2;
			if (mid * (1.0/X - 1.0/Y) >= 1)
				r = mid;
			else
				l = mid;
		}
		printf("%.0lf\n", ceil(mid/X));
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11869 - SOAP Response

Problem

給一個 SOAP 的回應格式，解析給定的回應，並且提供屬性查找。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
8
<a good="true" wants="no">
<b>
<c contest="running">
<d ballon="no">
</d>
</c>
</b>
</a>
4
a.b.c.d["ballon"]
a.c["contest"]
a.b.c["contest"]
c["contest"]

Sample Output

1
2
3
4
5
Case 1:
no
Undefined
running
Undefined

Solution

SOAP 類似 HTML XML 那種，在不少網路上的諮詢服務都會有這一套規則。

不過看到這一道題目很簡單，保證輸入格式一定可以相互匹配且完整，那使用遞迴 parsing 輸入，建造一個 tree 出來，同時子樹不會出現相同的命名。

建造樹出來之後，詢問就沿著樹走訪即可。

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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct Node {
	string name;
	map<string, string> attr;
	vector<int> son;
	void init() {
		attr.clear();
		son.clear();
	}
};
Node node[32767];
int nodesize;
char s[1024];
void parsingAttr(string line, Node &p) {
	string ign = "<>=", attr, val;
	for (int i = 0; i < line.length(); i++) {
		if (ign.find(line[i]) != string::npos) {
			line[i] = ' ';
		}
	}
	stringstream sin(line);
	sin >> p.name;
	while (sin >> attr >> val) {
		p.attr[attr] = val.substr(1, val.length()-2);
//		cout << attr << "+++" << val << endl;
	}
}
int build(string line) {
	int label = ++nodesize;
	Node &p = node[label];
	p.init();
	parsingAttr(line, p);
	while (gets(s)) {
		if (s[1] == '/')
			break;
		p.son.push_back(build(s));
	}
	return label;
}
int main() {
	int testcase, cases = 0, n, m;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		while(getchar() != '\n');
		gets(s);
		nodesize = 0;
		int root = build(s);
		scanf("%d", &m);
		while (getchar() != '\n');
		printf("Case %d:\n", ++cases);
		while(m--) {
			gets(s);
			string ign = ".[]", token;
			for (int i = 0; s[i]; i++) {
				if (ign.find(s[i]) != string::npos) {
					s[i] = ' ';
				}
			}
			stringstream sin(s);
			int pos = root;
			string res = "Undefined";
			sin >> token;
			if (token == node[pos].name) {
				while (sin >> token) {
					if (token[0] == '"') {
						string a = token.substr(1, token.length()-2);
						if (node[pos].attr.find(a) != node[pos].attr.end())
							res = node[pos].attr[a];
						break;
					} else {
						int f = 0;
						for (int i = 0; i < node[pos].son.size(); i++) {
							if (token == node[node[pos].son[i]].name) {
								f = 1;
								pos = node[pos].son[i];
								break;
							}
						}
						if (!f)
							break;
					}
				}
			}
			printf("%s\n", res.c_str());
		} 
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11651 - Krypton Number System

Problem

  • 相鄰數字不可相同
  • 不可前導為 0
  • score 分數為任兩個相鄰位數相減平方的總和

請問在 base 下，指定 score 的數字有多少個。

Sample Input

1
2
3
2
6 1
5 5

Sample Output

1
2
Case 1: 9
Case 2: 80

Solution

首先，可以知道每一次增加的總數最多為 (base - 1) (base - 1)，因此我們的狀態紀錄之少要追溯到當前分數 n - (base - 1) (base - 1)。

然而由於 score 過大，不可直接著手 dp[score][tail_digit] 之類的 dp 計算。仍可以計算於 (base - 1) * (base - 1) 以下的情況。

接著，利用遞迴公式 (線性變換矩陣 ?)，每一項為 a[score][tail_digit]，而分數必須保留到當前 score - (base - 1) * (base - 1)，因此狀態將會有 (base - 1) * (base - 1) * base，也就是矩陣最大上限 5 * 5 * 6 = 150。

矩陣的部分，可以假想每一次在尾數多增加一個 digit 上去，而在初始項部分仍必須依靠 dp 去計算。矩陣快速乘法直接套用 D&C 在 O(n^3 log k) 完成，並且計算時，盡可能將無用的 0 忽略計算，否則很容易 TLE。

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
#include <stdio.h> 
#include <string.h>
const unsigned long long mod = 1LLU<<32;
struct Matrix {
	unsigned long long v[150][150];
	int row, col; // row x col
	Matrix(int n, int m, long long a = 0) {
		memset(v, 0, sizeof(v));
		row = n, col = m;
		for(int i = 0; i < row && i < col; i++)
			v[i][i] = a;
	}
	Matrix operator*(const Matrix& x) const {
		Matrix ret(row, x.col);
		for(int i = 0; i < row; i++) {
			for(int k = 0; k < col; k++) {
				if (v[i][k])
				for(int j = 0; j < x.col; j++) {
					ret.v[i][j] += v[i][k] * x.v[k][j],
					ret.v[i][j] %= mod;
				}
			}
		}
		return ret;
	}
	Matrix operator^(const int& n) const {
		Matrix ret(row, col, 1), x = *this;
		int y = n;
		while(y) {
			if(y&1)	ret = ret * x;
			y = y>>1, x = x * x;
		}
		return ret;
	}
};
int main() {
	int testcase, cases = 0, base, score;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &base, &score);
		printf("Case %d: ", ++cases);
		int N = (base - 1) * (base - 1);
		
		unsigned long long dp[64][64] = {}; // [sum][tail_digit] = #way 
		for (int i = 0; i <= N; i++)
			dp[0][i] = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < base; j++) {
				for (int k = 0; k < base; k++) {
					int d = (j - k) * (j - k);
					if (i + d > N || j == k)
						continue;
					dp[i+d][k] += dp[i][j];
					dp[i+d][k] %= mod;
				}
			}
		}
		
		if (score <= N) {
			unsigned long long ret = 0;
			for (int i = 1; i < base; i++)
				ret = (ret + dp[score][i])%mod;
			printf("%llu\n", ret);
			continue;
		}
		int r, c;
		r = c = (base - 1) * (base - 1) * base;
		Matrix x(r, c), y(c, 1);
		for (int i = 1; i <= N; i++)
			for (int j = 0; j < base; j++)
				y.v[(i-1) * base+j][0] = dp[i][j];
		for (int i = base; i < r; i++)
			x.v[i - base][i] = 1;
		for (int i = 0; i < base; i++) {
			for (int j = 0; j < base; j++) {
				if (i == j)	continue;
				int d = N - (i - j) * (i - j);
				x.v[(N-1)*base + i][d*base + j] = 1;
			}
		}
//		puts("");
//		for (int i = 0; i < r; i++, puts(""))
//			for (int j = 0; j < c; j++)
//				printf("%lld ", x.v[i][j]);
//		for (int i = 0; i < c; i++, puts(""))
//				printf("%lld ", y.v[i][0]);
		Matrix z = (x ^ (score - N)) * y;
		unsigned long long ret = 0;
		for (int i = 1; i < base; i++)
			ret = (ret + z.v[(N-1) * base + i][0])%mod;
		printf("%llu\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11097 - Poor My Problem!

Problem

給一張圖 (有向圖)，請問從起始點走到特定點的路徑，花費 / 經過邊數 最小值為何？

並且最多經過 1000 條邊 (含)，邊可以重複走。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3 2 0
0 1 100
1 2 200
3
0
1
2
 
5 5 0
0 1 3
1 2 4
2 3 5
2 4 6
4 3 1
2
2
3

Sample Output

1
2
3
4
5
6
0.0000 0
100.0000 1
150.0000 2
3.5000 2
3.5000 4

Solution

如果沒有限制最多經過的邊，將會相當難辦事，因為一直繞就可以將平均值拉下，而會繞多久可能要玩一下環狀收斂，最小平均環，然後檢查是否會經過這個環抵達目的地 …

當然這一題已經給定最大使用邊數，定義狀態為 dp[i][j] 使用 j 條邊抵達目的地 i 的最小花費。按照 spfa 的精神不斷更新即可。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
	int to, w;
	edge(int a = 0, int b = 0):
		to(a), w(b) {}
};
vector<edge> g[1024];
int dp[1024][1024], inq[1024][1024];
const int MAXE = 1000;
void solve(int source, int N) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j <= MAXE; j++)
			dp[i][j] = 0x3f3f3f3f;
	queue<int> X, E;
	int u, v, w, e;
	dp[source][0] = 0;
	X.push(source), E.push(0);
	while (!X.empty()) {
		u = X.front(), X.pop();
		e = E.front(), E.pop();
		inq[u][e] = 0;
		if (e == MAXE)	continue;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i].to, w = g[u][i].w;
			if (dp[v][e+1] > dp[u][e] + w) {
				dp[v][e+1] = dp[u][e] + w;
				if (!inq[v][e+1]) {
					inq[v][e+1] = 1;
					X.push(v), E.push(e+1);
				}
			}
		}
	}
}
int main() {
	int N, M, S, Q;
	int x, y, w;
	while (scanf("%d %d %d", &N, &M, &S) == 3) {
		for (int i = 0; i < N; i++)
			g[i].clear();
		for (int i = 0; i < M; i++) {
			scanf("%d %d %d", &x, &y, &w);
			g[x].push_back(edge(y, w));
		}
		
		solve(S, N);
		
		scanf("%d", &Q);
		while (Q--) {
			scanf("%d", &x);
			double ret = 1e+30;
			int e = -1;
			if (x == S)
				ret = 0, e = 0;
			else {
				for (int i = 1; i <= MAXE; i++) {
					if (dp[x][i] != 0x3f3f3f3f) {
						if ((double)dp[x][i]/i < ret) {
							ret = (double)dp[x][i]/i;
							e = i;
						}
					}
				}
			}
			if (e == -1)
				puts("No Path");
			else
				printf("%.4lf %d\n", ret, e);
		}
		puts("");
	}
	return 0;
}
Read More +