题目描述也不写清楚。。。
考慮了空行没考慮全空格的行。。。不看discuss谁想得到这个还在de祘法的bug呢。。。
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
using namespace std;

int main() {
	int T;
	cin >> T;
	for(int ii = 0; ii < T; ii++){
		int n;
		cin >> n;
		int adj[110][110];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cin >> adj[i][j];
			}
		}
		int sp[110];
		int spn = 0;
		string s;
		while(1){
			while(getline(cin, s)){
				if(s.length()) break;
			}
			stringstream ss;
			ss << s;
			while(ss >> sp[spn]){
				spn++;
			}
			if(spn) break;
		}
		//for(int i = 0; i < spn; i++) cout << sp[i] << " "; cout << endl;
		int dest = sp[spn-1];
		//cout << dest << endl;
		int minDist[110];
		minDist[spn-1] = 0;
		for(int i = spn-2; i >= 0; i--){
			minDist[i] = adj[sp[i]][sp[i+1]] + minDist[i+1];
		}
		//for(int i = 0; i < spn; i++) cout << minDist[i] << " " ; cout << endl;
		int maxDetour = 0;
		for(int i = 0; i < spn-1; i++){
			//最小距离是minDist[i]
			//下面是dj
			int estmDist[110];
			for(int j = 1; j <= n; j++) estmDist[j] = 2147483647;
			estmDist[sp[i]] = 0;
			for(int j = 1; j <= n; j++){
				if(j == sp[i+1]) continue;
				if((adj[sp[i]][j] > 0) && (adj[sp[i]][j] < estmDist[j])) estmDist[j] = adj[sp[i]][j];
			}
			bool used[110] = {0};
			used[sp[i]] = 1;
			for(int j = 0; j < n-1; j++){
				int mnDist = 2147483647, arg = -1;
				for(int k = 1; k <= n; k++){
					if(used[k]) continue;
					if(estmDist[k] < mnDist){
						mnDist = estmDist[k];
						arg = k;
					}
				}
				if(arg == -1) break;
				used[arg] = 1;
				if(arg == dest) break;
				for(int k = 1; k <= n; k++){
					if(used[k]) continue;
					if((adj[arg][k] > 0) && (estmDist[k] > estmDist[arg] + adj[arg][k])){
						estmDist[k] = estmDist[arg] + adj[arg][k];
					}
				}
			}
			int detour = estmDist[dest] - minDist[i];
			if(maxDetour < detour) maxDetour = detour;
		}
		cout << maxDetour << endl;
	}
	return 0;
}