1411 . Dijkstra（駭客題）
TopCoder
Tags
Description
眾所周知 Dijkstra 演算法是一個能夠求得最短路的演算法，被廣泛使用在所有邊的邊權非負的時候。很多人會以為 Dijkstra 演算法在圖有負環的時候才會出現問題，但事實上只要圖有負邊就可能會讓 Dijkstra 演算法退化成指數時間複雜度。至於原因嘛，你為什麼不要試著自己找找看呢？
所以現在，以下為一個能夠用 Dijkstra 演算法得出從節點 $1$ 到節點 $2$ 的最短路的程式碼，請生成一張點數至多為 $31$ 且沒有負環的有向簡單圖使得程式執行結束後，變數 iter 儘量大。
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, m;
cin >> n >> m;
vector <vector <pair <int, int>>> adj(n + 1);
for (int i = 0, u, v, w; i < m; ++i) {
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
using T = pair<long long, int>;
const long long inf = numeric_limits<long long>::max() / 2;
priority_queue <T, vector <T>, greater<>> pq;
vector <long long> dis(n + 1, inf);
auto push = [&](int v, int d) {
if (dis[v] <= d) return;
dis[v] = d;
pq.emplace(dis[v], v);
};
push(1, 0);
long long iter = 0;
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
iter++;
if (dis[v] < d) continue;
for (auto [u, w] : adj[v]) {
push(u, d + w);
}
}
if (dis[2] == inf) cout << "Not Found\n";
else cout << dis[2] << "\n";
}
假設最後變數 iter 的值為 $x$，那麼你會獲得
$$
e + \frac{1208}{\sqrt{1 + 208}} \times \left(1 + \tanh\left((\log_{2}x)^ {1.208 / e} - \sqrt{1 + 2 + 0 + 8}\right) \right)
$$
分。注意到在本題中你可能可以獲得超過 $100$ 分，而你的分數超過 $100$ 分就會獲得 AC。我們保證至少存在一種輸入可以獲得超過 $100$ 分。
Input Format
輸入第一行有兩個正整數 $n, m$，代表圖的點數與邊數。
接下來 $m$ 行每行有三個整數 $u_i, v_i, w_i$，代表第 $i$ 條邊為從節點 $u_i$ 到節點 $v_i$ 的有向邊，且邊權為 $w_i$。
- $2 \leq n \leq 31$
- $0 \leq m \leq n \times (n - 1)$
- $1 \leq u_i, v_i \leq n$
- $-10^ 9 \leq w_i \leq 10^ 9$
- 圖為簡單圖，也就是說圖沒有自環或是重邊。
- 圖沒有負環。
Output Format
輸入一個整數代表節點 $1$ 到節點 $2$ 的最短路，若不存在從節點 $1$ 到節點 $2$ 的路徑則輸出 Not Found。
Sample Input 1
3 2 1 2 -1 2 3 1
Sample Output 1
-1
Hints
$y = f(2^ x)$ 的函數如下圖：
以下程式碼能產生本題合法但獲得的分數不高的測試資料：
#include <stdio.h>
int main() {
puts("3 2");
puts("1 2 -1");
puts("2 3 1");
}
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 無額外限制。 | 100 |