LightOJ 1074 - Extended Traffic（spfa判負環 + dfs染色 + 最短路）

這一晚，TT 做了個美夢！

在夢中，TT 的願望成真了，他成為了喵星的統領！喵星上有 N 個商業城市，編号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。

喵星上共有 M 條有向道路供商業城市互相往來。但是随着喵星商業的日漸繁榮，有些道路變得非常擁擠。正在 TT 為之苦惱之時，他的魔法小貓咪提出了一個解決方案！TT 欣然接受并針對該方案頒布了一項新的政策。

具體政策如下：對每一個商業城市标記一個正整數，表示其繁榮程度，當每一隻喵沿道路從一個商業城市走到另一個商業城市時，TT 都會收取它們（目的地繁榮程度 - 出發地繁榮程度）^ 3 的稅。

TT 打算測試一下這項政策是否合理，是以他想知道從首都出發，走到其他城市至少要交多少的稅，如果總金額小于 3 或者無法到達請悄咪咪地打出 ‘?’。

Input

第一行輸入 T，表明共有 T 組資料。（1 <= T <= 50）

對于每一組資料，第一行輸入 N，表示點的個數。（1 <= N <= 200）

第二行輸入 N 個整數，表示 1 ～ N 點的權值 a[i]。（0 <= a[i] <= 20）

第三行輸入 M，表示有向道路的條數。（0 <= M <= 100000）

接下來 M 行，每行有兩個整數 A B，表示存在一條 A 到 B 的有向道路。

接下來給出一個整數 Q，表示詢問個數。（0 <= Q <= 100000）

每一次詢問給出一個 P，表示求 1 号點到 P 号點的最少稅費。

Output

每個詢問輸出一行，如果不可達或稅費小于 3 則輸出 ‘?’。

Sample Input

2

5

6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

10

1 2 4 4 5 6 7 8 9 10

10

1 2

2 3

3 1

1 4

4 5

5 6

6 7

7 8

8 9

9 10

2

3 10

Sample Output

Case 1:

3

4

Case 2:

?

?

題目大意：

首先輸入一個T 表示有T組測試用例，對于每一組樣例，先輸入一個n表示點的個數，然後輸入 n 個整數，表示w1 - wn 的權值，之後輸入一個m，表示有向邊的條數，然後輸入m行，每行輸入a b 表示a b 之間存在一條有向邊，需要注意的是，從a到b 的代價是（w[b] - w[a]）3 （粗心看成了異或，就離譜）。輸入一個Q，表示有Q次詢問，對于每一次詢問輸入一個P，如果不能到達或到達的代價小于3則輸出 ‘ ？’ 否則輸出到P的最短距離。

解題思路：

這道題門道很多，需要注意以下幾點。

1. 因為每個點都有權值，a 到 b 的代價是(w[b] - w[a])3 ，是以建圖時應該注意權值問題，然後這裡是3次方，第一次看成了異或T.T ，一定要注意
2. 權值相減有可能出現負數！不能用dijkstra了
3. 這道題的不能到達有兩種情況：第一是不能到達，即距離為inf，第二就是負環負環負環！此時也不能到達，這裡要用spfa判負環。
4. 關于出現負環後的處理，這裡用染色法，将出現負環的點的連通分量全部染色，遇到被染色的點直接跳過！
5. 多組樣例，每次不要忘記初始化。

一道很好的題，結合了很多知識點，也有很多坑，調出來收獲還是滿大的，注意以上的點再套spfa的闆子就能AC啦

Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define lowbit(x) x & (-x)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 50;
const int M = 200 + 50;

int h[N], ne[N], e[N], w[N], idx;
int dis[N], a[N], cnt[N];
bool vis[N], col[N];
int T, n, m;

void init()
{
	idx = 0;
	memset(h, -1, sizeof h);
	memset(cnt, 0, sizeof cnt);
	memset(col, false, sizeof col);
}

void add(int a, int b, int c)
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}

void dfs(int u)//将負環所在的連通分量染色
{
	col[u] = true;

	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (!col[j]) dfs(j);
	}

	return;
}

void spfa()
{
	memset(vis, false, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;

	queue<int > q;
	q.push(1);
	vis[1] = true;

	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		vis[t] = false;
		if (col[t]) continue;

		for (int i = h[t]; ~i; i = ne[i])
		{	
			int j = e[i];
			if (dis[t] + w[i] < dis[j])
			{
				dis[j] = dis[t] + w[i];
				cnt[j] = cnt[t] + 1;

				if (!vis[j])
				{	if (cnt[j] >= n) dfs(j);//不要忘記判負環
					q.push(j);
					vis[j] = true;
				}
			}
		}
	}
}

int main()
{
	int cs = 0;
	scanf("%d", &T);

	while (T --)
	{
		init();//多組初始化一下

		scanf("%d", &n);

		for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);

		scanf("%d", &m);

		while (m --)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			add(u, v, (a[v] - a[u]) * (a[v] - a[u]) * (a[v] - a[u]));
		}

		spfa();

		printf("Case %d:\n", ++cs);

		int q1;
		scanf("%d", &q1);

		while (q1 --)
		{
			int op;
			scanf("%d", &op);

			if (dis[op] < 3 || dis[op] == inf || col[op]) puts("?");
			else printf("%d\n", dis[op]);
		}
	}

	return 0;
}