POJ 1502

• 题意:求最短路中的 最大值 ，模板题

1. dij

    #include <iostream>
   #include <string.h>
   #include <queue>
   
   using namespace std;
   const int maxn = 105;
   const int MAX = 0x3f3f3f3f;
   
   int n;
   int e[maxn][maxn];
   int dist[maxn];
   bool vis[maxn];
   
   int dij() {
   	memset(vis,0,sizeof vis);
   	memset(dist,0x3f,sizeof dist);
   	dist[1] = 0; 
   	priority_queue<pair<int,int> > que;
   	que.push( make_pair(-dist[1],1) );
   	while (!que.empty()) {
   		int cur = que.top().second; que.pop();
   		if (vis[cur]) continue;
   		vis[cur] = 1;
   		for (int j=1; j<=n; j++) 
   			if (dist[j] > dist[cur]+e[cur][j]) {
   				dist[j] = dist[cur] + e[cur][j];
   				que.push( make_pair(-dist[j],j) );
   			}
   	}
   	int ans = 0;
   	for (int i=1; i<=n; i++) 
   		if (ans < dist[i] && dist[i] != MAX) ans = dist[i];
   	return ans;
   }
   
   int main() {
   //	freopen("a.txt","r",stdin);
   	cin >> n;
   	char str[10];
   	memset(e,0x3f,sizeof e);
   	for (int i=2; i<=n; i++) {
   		for (int j=1; j<=i-1; j++) {
   			scanf("%s",str);
   			if (str[0] == 'x') continue;
   			else {
   				int len = strlen(str);
   				int ans = 0;
   				for (int k=0; k<len; k++) {
   					ans += str[k] - '0';
   					if (k != len-1) ans *= 10;
   				}
   				e[i][j] = e[j][i] = ans;
   			}
   		}
   	}
   	printf("%d\n",dij());
   	return 0;
   }

2. floyd

    #include <iostream>
   #include <string.h>
   #include <string>
   #include <sstream>
   
   using namespace std;
   const int maxn = 105;
   const int MAX = 0x3f3f3f3f;
   int n;
   int e[maxn][maxn];
   int dist[maxn];
   
   int floyd () {
   	for (int k=1; k<=n; k++) 
   		for (int i=1; i<=n; i++)
   			for (int j=1; j<=n; j++)
   				e[i][j] = min(e[i][j],e[i][k]+e[k][j]);
   	int ans = 0;
   	for (int i=1; i<=n; i++) 
   		if (e[1][i] > ans && e[1][i] != MAX) ans = e[1][i];
   	return ans;
   }
   
   int main() {
   //	freopen("a.txt","r",stdin);
   	cin >> n;
   	char str[10];
   	memset(e,0x3f,sizeof e);
   	for (int i=2; i<=n; i++) {
   		for (int j=1; j<=i-1; j++) {
   			scanf("%s",str);
   			if (str[0] == 'x') continue;
   			else {
   				int len = strlen(str);
   				int ans = 0;
   				for (int k=0; k<len; k++) {
   					ans += str[k] - '0';
   					if (k != len-1) ans *= 10;
   				}
   				e[i][j] = e[j][i] = ans;
   			}
   		}
   	}
   	printf("%d\n",floyd());
   	return 0;
   }