Silver Cow Party
POJ-3268
- 这题也是最短路的模板题,只不过需要进行两次求解最短路,因为涉及到来回的最短路之和。
- 该题的求解关键是:求解B-A的最短路时,可以看做A是起点,这就和求解A-B的最短路很类似了,只不过需要将单向路的距离调换一下即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1111111111;
int w[1001][1001];//d[i][j]表示i到j的距离
int d[1001];//d[i]表示s到i的最短近距离
int v[1001];//v[i]表示是否被访问过
int n;//表示顶点数
void dijkstra(int s) {
for (int i = 0; i<n; i++) {
if (i == s)
d[i] = 0;
else
d[i] = INF;
}
memset(v, 0, sizeof(v));
for (int i = 0; i<n; i++) {
int x, m = INF;
for (int y = 0; y<n; y++)
if (!v[y] && d[y] <= m)
m = d[x = y];
v[x] = 1;
for (int y = 0; y<n; y++)
d[y] = min(d[y], d[x] + w[x][y]);
}
}
int main() {
int m, x;
cin >> n >> m >> x;
int a, b;
int weight;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
w[i][j] = INF;
if (i == j)
w[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
cin >> a >> b>>weight;
w[a-1][b-1] = weight;
}
dijkstra(x - 1);
int to[1001];
int back[1001];
for (int i = 0; i < n; i++)
back[i] = d[i];
/*for (int i = 0; i < n; i++) {
dijkstra(i);
to[i] = d[x - 1];
}*/
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int temp = w[i][j];
w[i][j] = w[j][i];
w[j][i] = temp;
}
}
dijkstra(x - 1);
int max=0, max_i=0;
for (int i = 0; i < n; i++) {
if (max < d[i] + back[i]) {
max = d[i] + back[i];
max_i = i;
}
}
cout << max << endl;
return 0;
}
JAVA:
package POJ;
import java.util.*;
public class POJ_3268 {
static int n,m,x;//n:1000,m:100000
static final int INF = 1111111111;
static int [][]w;//d[i][j]表示i到j的距离
static int []d;//d[i]表示s到i的最短近距离
static int []v;//v[i]表示是否被访问过
static void dijkstra(int s) {
for (int i = 0; i<n; i++) {
if (i == s)
d[i] = 0;
else
d[i] = INF;
}
Arrays.fill(v, 0);//这里很重要,因为v曾经改变过
for (int i = 0; i<n; i++) {
int x=0, m = INF;
for (int y = 0; y<n; y++)
if (v[y]==0 && d[y] <= m)
m = d[x = y];
v[x] = 1;
for (int y = 0; y<n; y++)
d[y] = Math.min(d[y], d[x] + w[x][y]);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
n=cin.nextInt();m=cin.nextInt();x=cin.nextInt();
w=new int[n][n];
d=new int[n];
v=new int[n];
int a, b;
int weight;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
w[i][j] = INF;
if (i == j)
w[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
a=cin.nextInt();b=cin.nextInt();weight=cin.nextInt();
w[a-1][b-1] = weight;
}
dijkstra(x - 1);
int []to=new int[n];
int []back=new int[n];
for (int i = 0; i < n; i++)
back[i] = d[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int temp = w[i][j];
w[i][j] = w[j][i];
w[j][i] = temp;
}
}
dijkstra(x - 1);
int max=0, max_i=0;
for (int i = 0; i < n; i++) {
if (max < d[i] + back[i]) {
max = d[i] + back[i];
max_i = i;
}
}
System.out.println(max);
}
}