#include <iostream>
#include <stdio.h>
using namespace std;

int adjQuList[1010][1010];
int adjQuDist[1010][1010];
int adjQuNum[1010] = {0};
int adjFeiList[1010][1010];
int adjFeiDist[1010][1010];
int adjFeiNum[1010] = {0};

int main() {
	int N, M, X;
	scanf("%d%d%d", &N, &M, &X);
	for(int i = 0; i < M; i++){
		int from, to, dist;
		scanf("%d%d%d", &from, &to, &dist);
		adjQuList[from][adjQuNum[from]] = to;
		adjQuDist[from][adjQuNum[from]] = dist;
		adjQuNum[from]++;
		adjFeiList[to][adjFeiNum[to]] = from;
		adjFeiDist[to][adjFeiNum[to]] = dist;
		adjFeiNum[to]++;
	}
	int quDist[1010], feiDist[1010];
	for(int i = 1; i <= N; i++){
		quDist[i] = 1000000000;
	}
	for(int j = 1; j <= N; j++){
		feiDist[j] = 1000000000;
	}
	quDist[X] = feiDist[X] = 0;
	bool quUsed[1010] = {0}, feiUsed[1010] = {0};
	for(int i = 1; i <= N; i++){
		int mn = 2147483647, arg = -1;
		for(int j = 1; j <= N; j++){
			if(quUsed[j]) continue;
			if(quDist[j] < mn){
				mn = quDist[j];
				arg = j;
			}
		}
		quUsed[arg] = 1;
		for(int j = 0; j < adjQuNum[arg]; j++){
			if(quUsed[adjQuList[arg][j]]) continue;
			int newDist = quDist[arg] + adjQuDist[arg][j];
			if(newDist < quDist[adjQuList[arg][j]]){
				quDist[adjQuList[arg][j]] = newDist;
			}
		}
	}
	for(int i = 1; i <= N; i++){
		int mn = 2147483647, arg = -1;
		for(int j = 1; j <= N; j++){
			if(feiUsed[j]) continue;
			if(feiDist[j] < mn){
				mn = feiDist[j];
				arg = j;
			}
		}
		feiUsed[arg] = 1;
		for(int j = 0; j < adjFeiNum[arg]; j++){
			if(feiUsed[adjFeiList[arg][j]]) continue;
			int newDist = feiDist[arg] + adjFeiDist[arg][j];
			if(newDist < feiDist[adjFeiList[arg][j]]){
				feiDist[adjFeiList[arg][j]] = newDist;
			}
		}
	}
	int mx = 0;
	for(int i = 1; i <= N; i++){
		int tmp = quDist[i] + feiDist[i];
		if(tmp > mx) mx = tmp;
	}
	printf("%d\n", mx);
	return 0;
}

• Re:两次DJ，㞎下标竟然打反了嚷昂一次。。。（这题要2000ms干啥？） (2063) 16310120805 2017-08-08 12:52:39