POJ 1502 - MPI Maelstrom（鍊式前向星 + dijkstra模闆題）

由于叛徒朱子明的出賣，導緻獨立團在趙家峪的團部駐軍在團長李雲龍大婚之日幾乎全軍覆沒，突出重圍之後，李雲龍決定集合所有駐紮在外的部隊，使用重型武器意大利炮攻打平安縣城，消息從團部傳出之後到達各部駐地之後，駐地長官會派出自己的通訊人員通知其他駐地部隊，自團部派人傳達指令開始，至少經過多長時間才能使得所有駐紮在外的部隊受到指令。（假設通訊員在路上不會遭遇任何意外）

Input

第一行輸入一個n，表示包括團部在内有多少不同的駐軍（團部當然是編号為1了）。

随後n-1行，以鄰接矩陣的形式給出各駐軍（1 ~ n）之間派遣通訊員需要的時間。

由于兩地駐軍派遣通訊員所需時間相等（從一營三連駐地到二營一連駐地和二營一連駐地到一營三連駐地所需時間是一樣的），且駐地自己和自己不需要派遣通訊員，是以隻給出了矩陣的下三角。

x表示由于部分駐地之間因特殊原因不能派遣通訊員，比如途中需要經過敵占區

該題所有資料範圍0 ~ 100。

Output

輸出一行表示所有駐地都受到來自團部的指令所需要的時間。

Sample Input

5

50

30 5

100 20 50

10 x x 10

Sample Output

35

題目大意：

這道題首先要注意一下輸入，輸入和以往圖論不太一樣，給出了鄰接矩陣的下三角，并且題目已經說明兩駐紮地時間相等，是以兩地是雙向連通的，是以建雙向邊，需要從1出發将消息送往各個駐紮地，消息是并行傳輸，是以隻需要各個點取最短時間的最大值即可。

PS：數組開小了調了一下午，紀念一下T.T

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 = 1e4 + 50;
const int M = 1e4 + 50;

int h[N], ne[N], e[N], w[N], idx;
int dis[N];
bool vis[N];
int n;

inline int read()//改一下快讀闆子即可正确處理 x 字元
{
	char c = getchar();
	if (c == 'x') return inf;

	int res = 0;
	while (!isdigit(c))
	{
		c = getchar();
		if (c == 'x') return inf;
	}
		
	while (isdigit(c)) res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	
	return res;
}

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

void dijkstra(int s)//最短路模闆題
{
	memset(dis, 0x3f, sizeof dis);

	dis[s] = 0;

	priority_queue<pii, vector<pii >, greater<pii > > q;
	q.push({0, 1});

	while (!q.empty())
	{
		pii t = q.top();
		q.pop();

		int u = t.second, v = t.first;
		if (vis[u]) continue;
		vis[u] = true;

		for (int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if (v + w[i] < dis[j])
			{
				dis[j] = v + w[i];
				q.push({dis[j], j});
			}
		}
	}
}

int main()
{
	memset(h, -1, sizeof h);
	n = read();

	for (int i = 2; i <= n; i ++)
		for (int j = 1; j < i; j ++)
		{
			int val = read();
			if (val == inf) continue;

			add(i, j, val);
			add(j, i, val);
		}

	dijkstra(1);

	int ans = 0;

	for (int i = 2; i <= n; i ++) ans = max(ans, dis[i]);

	printf("%d\n", ans);

	return 0;
}