poj 3268

• 暴力:每个点都用一次dij,去的时间是该点到终点的路径,回来的时间是终点到每个点的路径,加起来找到最大值,
  果然TLE

  #include <iostream>
  #include <algorithm>
  #include <string.h>
  #include <queue>
  
  using namespace std;
  const int maxn = 1001;
  
  int time[maxn];
  int e[maxn][maxn];
  bool vis[maxn];
  int dist[maxn];
  int n,end,m;
  
  void dij(int x) {
  	memset(vis,0,sizeof vis);
  	memset(dist,0x3f,sizeof dist);
  	dist[x] = 0;
  	priority_queue<pair<int,int> > que;
  	que.push(make_pair( -dist[x],x) );
  	while ( !que.empty() ) {
  		int cur = que.top().second;
  		que.pop();
  		if (vis[cur]) continue;
  		vis[cur] = 1;
  		for (int i=1; i<=n; i++) {
  			int to = i;
  			int div = e[cur][i];
  			if (div + dist[cur] < dist[to]) {
  				dist[to] = div + dist[cur];
  				que.push(make_pair(-dist[to],to));
  			}
  		}
  	}
  	if (x == end) { //回去的时间,每个人都要加
  		for (int i=1; i<=n; i++) 
  			if (i != end) //除去end点,每头牛+回去的时间 
  				time[i] += dist[i];
  	}
  	else { //去的时间只是x到end的
  		time[x]+=dist[end];
  	}
  }
  void read() {
  	memset(e,0x3f,sizeof e);
  	scanf("%d%d%d",&n,&m,&end);
  	for (int i=1; i<=m; i++) {
  		int u,v,w;
  		scanf("%d%d%d",&u,&v,&w);
  		e[u][v] = w;
  	}
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	read();
  	for (int i=1; i<=n; i++) 
  			dij(i);
  	time[end] = 0;
  	cout << *max_element(time+1,time+n+1);
  	return 0;
  }

• 由于去的时间计算太多次,
• 这里将矩阵转置一下,发现,去的时间就是dij(2)到每个点的距离,因为路径的方向全部取反,所以求出来的恰好是去的时间

  #include <iostream>
  #include <algorithm>
  #include <string.h>
  #include <queue>
  
  using namespace std;
  const int maxn = 1001;
  
  int time[maxn];
  int e[maxn][maxn];
  bool vis[maxn];
  int dist[maxn];
  int n,end,m;
  int backup[maxn][maxn];
  
  void dij(int x) {
  	memset(vis,0,sizeof vis);
  	memset(dist,0x3f,sizeof dist);
  	dist[x] = 0;
  	priority_queue<pair<int,int> > que;
  	que.push(make_pair( -dist[x],x) );
  	while ( !que.empty() ) {
  		int cur = que.top().second;
  		que.pop();
  		if (vis[cur]) continue;
  		vis[cur] = 1;
  		for (int i=1; i<=n; i++) {
  			int to = i;
  			int div = e[cur][i];
  			if (div + dist[cur] < dist[to]) {
  				dist[to] = div + dist[cur];
  				que.push(make_pair(-dist[to],to));
  			}
  		}
  	}
  	for (int i=1; i<=n; i++) 
  		if (i != end) //除去end点,每头牛+回去的时间 
  			time[i] += dist[i];
  }
  void read() {
  	memset(e,0x3f,sizeof e);
  	scanf("%d%d%d",&n,&m,&end);
  	for (int i=1; i<=m; i++) {
  		int u,v,w;
  		scanf("%d%d%d",&u,&v,&w);
  		e[u][v] = w;
  	}
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	read();
  	dij(end);
  	// 矩阵转置
  	for (int i=1; i<=n; i++)
  		for (int j=1; j<=n; j++) 
  			backup[j][i] = e[i][j];
  	for (int i=1; i<=n; i++)
  		for (int j=1; j<=n; j++) 
  			e[i][j] = backup[i][j];
  	dij(end);
  	cout << *max_element(time+1,time+n+1);
  	return 0;
  }