# 題目: UVa 10449 - Traffic

# 題目說明

給一個有向圖，圖中每個點皆有值，而從一個點移動到下一個點的cost為(目的點的值 - 當前點的值) * 3
求1到終點的最短路徑

---

INPUT:
每筆測資第一個輸入為整數n，代表有n個點
接下來有n個整數，代表從1 ~ n的點的值
第二行有一個整數m，代表有m條邊
接下來有m行，每行有兩個整數，代表前者連接到後者(單向)
最後有一個整數q，代表終點的數量
之後q個整數代表終點的位置

---

OUTPUT:
輸出從1到終點的最短路徑
如果最短路徑或無法找到，則輸出?

# 解題方法

先儲存個點的值及建圖
接著以bellman演算法找到最短路徑，如果有負的值，則push至unordered_set內

# 參考程式碼

#include <iostream>
#include <memory.h>
#include <vector>
#include <math.h>
#include <climits>
#include <unordered_set>

using namespace std;

vector< vector< pair<int, int> > > edge;
int busyness[201];
int dis[201];
unordered_set<int> store;

void bellman(int n)
{
	dis[1] = 0;

	for (int i = 0; i < n - 1; ++i) for (int u = 1; u <= n; ++u)
	{
		for (auto& [v, w] : edge[u]) if (dis[u] != INT_MAX) dis[v] = min(dis[v], dis[u] + w);
	}

	for (int u = 1; u <= n; ++u) for (auto& [v, w] : edge[u])
	{
		if (dis[v] > dis[u] + w)
		{
			dis[v] = dis[u] + w;
			store.emplace(v);
		}
	}

}

int main()
{
	// fast io 
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, cases = 0;
	while (cin >> n)
	{
		// init
		edge.assign(n + 1, vector< pair<int, int> >());
		memset(busyness, 0, sizeof(busyness));
		fill(dis, dis + 201, INT_MAX);
		store.clear();

		for (int i = 1, tmp; i <= n; ++i) cin >> tmp, busyness[i] = tmp;

		int m, u, v;
		cin >> m;
		while (m--) cin >> u >> v, edge[u].push_back({ v, pow(busyness[v] - busyness[u], 3.0)});

		bellman(n);

		cout << "Set #" << ++cases << "\n";
		int q, num;
		cin >> q;
		while (q--)
		{
			cin >> num;
			if (store.count(num) || dis[num] < 3 || dis[num] == INT_MAX) cout << "?\n";
			else cout << dis[num] << "\n";
		}
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2010449/