城市穿梭

序列操作

问题描述

有 N 个商业城市，编号 1 ～ N，其中 1 号城市是首都。
共有 M 条有向道路供商业城市相互往来。
对每一个商业城市标记一个正整数，表示其繁荣程度，当有人沿道路从一个商业城市走到另一个商业城市时，会被收取 (目的地繁荣程度 – 出发地繁荣程度)^3 的税。
求从首都出发，走到其他城市至少要交多少的税，如果总金额小于 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

Output: 
Case 1:
3
4
Case 2:
?
?

Limitation

Time limit		2000 ms
Memory limit	32768 kb

解题思路

含有负边的单源最短路问题，可以用Bellman-Ford算法解决。

Bellman-Ford Algorithm

从源点s开始，用dis[]数组初始化距离。dis[s] = 0，dis[v] = +∞ (v ≠ s)。
反复对边集E中的每条边进行松弛操作，使得点集V中的每个顶点v的最短距离估计值逼近其最短距离，共运行|V|-1次。
判断E中的每一条边的两个端点是否收敛，若有端点未收敛则无解，否则就将从源点可到达的v加入到dis[v]中。

伪代码

procedure BellmanFord(list vertices, list edges, vertex source)
   // 读入边和节点的列表并对distance和predecessor写入最短路径

   // 初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 对每一条边重复操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 检查是否有负权回路
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "图包含具负权重的回路"

举个例子

然而，Bellman-Ford算法的时间复杂度是O(|V|×|E|)，相比于Dijkstra太慢了，因此引入了队列优化的SPFA。

Shortest Path Fast Algorithm (SPFA)

SPFA总的期望时间复杂度为O(n log n log (m/n) + m)，基于实验获得的平均时间复杂度为O(2|E|)。(From Wikipedia))

给定一个加权有向图G，从源点s开始，求到每个顶点v的最短路径dis[v]。
基本思路与Bellman-Ford相同，只不过SPFA使用了队列维护备选节点，仅有节点被松弛后才会放入队列中。即如果这轮dis[i]没有被更新，那么下一轮就没有必要更新所有从i出发的边。如果某一点入队 n 次则说明有负环。

伪代码

procedure Shortest-Path-Faster-Algorithm(G, s)
 1    for each vertex v ≠ s in V(G)
 2        d(v) := ∞
 3    d(s) := 0
 4    offer s into Q
 5    while Q is not empty
 6        u := poll Q
 7        for each edge (u, v) in E(G)
 8            if d(u) + w(u, v) < d(v) then
 9                d(v) := d(u) + w(u, v)
10                if v is not in Q then
11                    offer v into Q

回到本题

根据繁荣程度，求出各个边的权值。题目要求从1到 i 的最短路径。若不可到达、可到达但税收小于3且不存在负环、可到达但存在负环则输出’?‘。

源代码

#include <iostream>
#include <queue>
using namespace std;

struct edge {
	int to, w;
	edge* next;
	edge() { to = -1; w = -1; next = NULL; }
	edge(int _t, int _w) :to(_t), w(_w) { next = NULL; }
};

class linkedList {
private:
	edge* head;
	int size;
public:
	linkedList() { head = NULL; size = 0; }
	~linkedList() {
		edge* temp = head;
		while (temp != NULL) {
			edge* p = temp;
			temp = temp->next;
			p = NULL;
			delete p;
		}
		delete temp;
		head = NULL;
		size = 0;
	}
	edge* getFirst() { return head; }
	void add(int to, int w) {
		edge* node = new edge(to, w);
		if (head == NULL) {
			head = node;
			return;
		}
		edge* p = head;
		edge* pp = NULL;
		while (p != NULL) {
			pp = p;
			p = p->next;
		}

		pp->next = node;
		size++;
	}
};

const int maxN = 210;
const int inf = 2e8;

class graph {
private:
	linkedList arr[maxN];
	int size;
	int dis[maxN];
	bool visit[maxN];
public:
	graph() { size = 0; }
	graph(int n) :size(n) {  }
	~graph() {  }
	void add(int a, int b, int w) {
		arr[a].add(b, w);
	}
	void dfs(int x) {
		for (edge* temp = arr[x].getFirst(); temp != NULL; temp = temp->next) {
			int y = temp->to;
			if (!visit[y]) {
				visit[y] = true;
				dfs(y);
			}
		}
	}
	void spfa() {
		queue<int> q;
		int inq[maxN] = { 0 };
		int cnt[maxN] = { 0 };//记录访问每个点经过边的次数
		for (int i = 0; i <= size; i++) {
			dis[i] = inf;
			visit[i] = false;
		}
			
		dis[1] = 0;
		q.push(1);
		while (!q.empty()) {
			int p = q.front();
			q.pop();
			inq[p] = 0;
			for (edge* temp = arr[p].getFirst(); temp != NULL; temp = temp->next) {
				int dest = temp->to;
				int weight = temp->w;
				if (visit[dest])
					continue;
				if (dis[dest] > dis[p] + weight) {
					dis[dest] = dis[p] + weight;
					cnt[dest] = cnt[p] + 1;
					if (cnt[dest] >= size) {//说明存在负环
						visit[dest] = true;
						dfs(dest);
					}
					if (!inq[dest]) {
						q.push(dest);
						inq[dest] = 1;
					}
				}
			}
		}
	}

	void output(int x) {
		if (visit[x] || dis[x] == inf || dis[x] < 3)
			cout << "?" << endl;
		else
			cout << dis[x] << endl;
	}
};

int main() {
	int t;
	cin >> t;
	for (int ii = 1; ii <= t; ii++) {
		int n, m, q;
		cin >> n;
		graph G(n);
		int* W = new int[n + 10];
		for (int i = 1; i <= n; i++)
			cin >> W[i];
		cin >> m;
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			int w0 = W[b] - W[a];
			int weight = w0 * w0 * w0;
			G.add(a, b, weight);
		}
		G.spfa();
		cout << "Case " << ii << ":" << endl;
		cin >> q;
		for (int i = 0; i < q; i++) {
			int p;
			cin >> p;
			G.output(p);
		}
	}
	return 0;
}