# 挑战程序竞赛系列（11）：2.5最短路径

## AOJ 0189: Convenient Location

```public class Main {

static final int MAX_LOC = 10;

public static void main(String[] args) throws IOException {
String line;
String[] words;

while ((line = br.readLine()) != null && !line.isEmpty()) {

int n = parseInt(line);
if (n == 0) break;

//init
long[][] g = new long[MAX_LOC][MAX_LOC];
int N = 0;

for (int i = 0; i < g.length; i++) {
for (int j = 0; j < g[i].length; j++) {
if (i != j) g[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < n; i++) {
words = br.readLine().split(" ");
int x, y, d;
x = parseInt(words[0]);
y = parseInt(words[1]);
d = parseInt(words[2]);
N = Math.max(N, Math.max(x, y));
g[y][x] = g[x][y] = d;
}

//solve
for (int k = 0; k <= N; k++) {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}

int pos = Integer.MAX_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i <= N; i++) {
int tmp = 0;
for (int j = 0; j <= N; j++) {
tmp += g[i][j];
}
if (tmp < min) {
pos = i;
min = tmp;
}
}

System.out.println(pos + " " + min);

}
}
}```

## POJ 2139: Six Degrees of Cowvin Bacon

```static int INF = 1 << 29;

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[][] g = new int[N][N];

for (int i = 0; i < N; ++i) Arrays.fill(g[i],INF);
for (int i = 0; i < N; ++i) g[i][i] = 0;

for (int i = 0; i < M; ++i){
int n = in.nextInt();
int[] x = new int[n];
for (int j = 0; j < n; ++j){
x[j] = in.nextInt();
x[j]--;
}
for (int k = 0; k < n; ++k){
for (int l = k + 1; l < n; ++l){
g[x[k]][x[l]] = g[x[l]][x[k]] = 1;
}
}
}

for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
for (int k = 0; k < N; ++k){
g[j][k] = Math.min(g[j][k],g[j][i] + g[i][k]);
}
}
}

int ans = INF;
for (int i = 0; i < N; ++i){
int sum = 0;
for (int j = 0; j < N; ++j){
sum += g[i][j];
}
ans = Math.min(ans, sum);
}

System.out.println(100 * ans / (N - 1));
}```

## POJ 3268: Sliver Cow Party

```static int INF = 1 << 29;
static int[][] g;
static int N;

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();

int M = in.nextInt();
int X = in.nextInt();
g = new int[N][N];
d = new int[N][N];
for (int i = 0; i < N; ++i) Arrays.fill(g[i], INF);
for (int i = 0; i < N; ++i) g[i][i] = 0;

for (int i = 0; i < M; ++i){
int f = in.nextInt();
int t = in.nextInt();
f--;
t--;
int c = in.nextInt();
g[f][t] = c;
}

warshallFloyd();

int max = 0;
for (int i = 0; i < N; ++i){
if (i == X) continue;
max = Math.max(max, g[i][X] + g[X][i]);
}
System.out.println(max);
}
private static void warshallFloyd(){
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
for (int k = 0; k < N; ++k){
g[j][k] = Math.min(g[j][k], g[j][i] + g[i][k]);
}
}
}
}```

TLE了，顶点数1000，所以需要执行100031000^3次，自然TLE，所以必须优化，采用DIJKSTRA算法，因为此题已经表明不存在负环，所以可以使用DIJKSTRA来计算任意两点之间的距离。

Dijkstra：假设所有边都为正，不存在负环。

```static int INF = 1 << 29;
static int[][] g;
static int[][] d;
static int N;

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();

int M = in.nextInt();
int X = in.nextInt();
g = new int[N][N];
d = new int[N][N];
for (int i = 0; i < N; ++i) Arrays.fill(g[i], INF);
for (int i = 0; i < N; ++i) g[i][i] = 0;

for (int i = 0; i < M; ++i){
int f = in.nextInt();
int t = in.nextInt();
f--;
t--;
int c = in.nextInt();
g[f][t] = c;
}

for (int i = 0; i < N; ++i){
//initial
Arrays.fill(d[i], INF);
d[i][i] = 0;
dijkstra(i);
}

int max = 0;
for (int i = 0; i < N; ++i){
if (i == X) continue;
max = Math.max(max, d[i][X] + d[X][i]);
}
System.out.println(max);
}

private static void dijkstra(int s){
int V = N;
boolean[] used = new boolean[V];
while (true){
int v = -1;
for (int i = 0; i < V; ++i){
if (!used[i] && (v == -1 || d[s][i] < d[s][v])) v = i;
}
if (v == -1) break;
used[v] = true;
for (int i = 0; i < V; ++i){
d[s][i] = Math.min(d[s][i],d[s][v] + g[v][i]);
}
}
}```

```static int INF = 1 << 29;
static int[][] d;
static List<Edge>[] graph;
static int N;

static class Edge{
int from;
int to;
int cost;

@Override
public String toString() {
return from + "->" + to + " ,cost: " + cost;
}
}

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();

int M = in.nextInt();
int X = in.nextInt();
graph = new ArrayList[N];

d = new int[N][N];
for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

for (int i = 0; i < M; ++i){
int f = in.nextInt();
int t = in.nextInt();
f--;
t--;
int c = in.nextInt();
Edge e = new Edge();
e.from = f;
e.to = t;
e.cost = c;
}

for (int i = 0; i < N; ++i){
//initial
Arrays.fill(d[i], INF);
d[i][i] = 0;
dijkstra(i);
}

int max = 0;
for (int i = 0; i < N; ++i){
if (i == X) continue;
max = Math.max(max, d[i][X] + d[X][i]);
}
System.out.println(max);
}

private static void dijkstra(int s){
int V = N;
IndexMinPQ<Integer> pq = new IndexMinPQ<>(V);
pq.insert(s, d[s][s]);
while (!pq.isEmpty()){
int v = pq.delMin();
for (Edge e : graph[v]){
int from = e.from;
int to = e.to;
int cost = e.cost;
if (d[s][from] + cost < d[s][to]){
d[s][to] = d[s][from] + cost;
if (pq.contains(to)) pq.decreaseKey(to, d[s][to]);
else pq.insert(to, d[s][to]);
}
}
}
}```

• 从X到每个顶点的最短距离，一次dijkstra(X)即可。
• 如果是无向图，任何顶点到X的最短距离，一定也是X到任何顶点的最短距离，所以此图可以来个反向，这样相当于求无向图中的顶点X到任何顶点的最短距离，再来一次dijkstra(X)，OK！

## AOJ 2249: Road Construction

```public class SolutionDay16_A2249 {

static class Edge{
int from;
int to;
int dist;
int cost;

@Override
public String toString() {
return "{"+from + "->" + to + ", dist: " + dist + "}";
}
}

static int INF = 1 << 29;
static List<Edge>[] graph;
static int[] dist;
static int N;

@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
N = in.nextInt();
int M = in.nextInt();
if (N == 0 && M == 0) break;
graph = new ArrayList[N];
for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

for (int i = 0; i < M; ++i){
int f = in.nextInt();
int t = in.nextInt();
f--;
t--;
int dist = in.nextInt();
int cost = in.nextInt();

Edge edge = new Edge();
edge.from = f;
edge.to = t;
edge.cost = cost;
edge.dist = dist;

edge = new Edge();
edge.from = t;
edge.to = f;
edge.cost = cost;
edge.dist = dist;
}

dijkstra(0);
long sum = 0;
for (int i = 1; i < N; ++i){
int min = INF;
for (Edge e : graph[i]){
if (dist[i] == dist[e.to] + e.dist && e.cost < min){
min = e.cost;
}
}
sum += min;
}
System.out.println(sum);
}
}

private static void dijkstra(int s){
dist = new int[N];
Arrays.fill(dist,INF);
dist[s] = 0;
IndexMinPQ<Integer> pq = new IndexMinPQ<>(N);
pq.insert(s, dist[s]);
while (!pq.isEmpty()){
int v = pq.delMin();
for (Edge e : graph[v]){
if (dist[e.from] + e.dist < dist[e.to]){
dist[e.to] = dist[e.from] + e.dist;
if (pq.contains(e.to)) pq.decreaseKey(e.to, dist[e.to]);
else pq.insert(e.to, dist[e.to]);
}
}
}
}

static class Scanner {

private StringTokenizer tok;

public Scanner(InputStream is) throws IOException {
getLine();
}

private void getLine() throws IOException {
while (tok == null || !tok.hasMoreTokens()) {
tok = new StringTokenizer(br.readLine());
}
}

private boolean hasNext() {
}

public String next() throws IOException {
if (hasNext()) {
} else {
getLine();
}
}

public int nextInt() throws IOException {
if (hasNext()) {
return Integer.parseInt(tok.nextToken());
} else {
getLine();
return Integer.parseInt(tok.nextToken());
}
}

public long nextLong() throws IOException {
if (hasNext()) {
return Long.parseLong(tok.nextToken());
} else {
getLine();
return Long.parseLong(tok.nextToken());
}
}

public double nextDouble() throws IOException {
if (hasNext()) {
return Double.parseDouble(tok.nextToken());
} else {
getLine();
return Double.parseDouble(tok.nextToken());
}
}
}

static class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
private int maxN;        // maximum number of elements on PQ
private int n;           // number of elements on PQ
private int[] pq;        // binary heap using 1-based indexing
private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;      // keys[i] = priority of i

/**
* Initializes an empty indexed priority queue with indices between {@code 0}
* and {@code maxN - 1}.
* @param  maxN the keys on this priority queue are index from {@code 0}
*         {@code maxN - 1}
* @throws IllegalArgumentException if {@code maxN < 0}
*/
@SuppressWarnings("unchecked")
public IndexMinPQ(int maxN) {
if (maxN < 0) throw new IllegalArgumentException();
this.maxN = maxN;
n = 0;
keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
pq   = new int[maxN + 1];
qp   = new int[maxN + 1];                   // make this of length maxN??
for (int i = 0; i <= maxN; i++)
qp[i] = -1;
}

/**
* Returns true if this priority queue is empty.
*
* @return {@code true} if this priority queue is empty;
*         {@code false} otherwise
*/
public boolean isEmpty() {
return n == 0;
}

/**
* Is {@code i} an index on this priority queue?
*
* @param  i an index
* @return {@code true} if {@code i} is an index on this priority queue;
*         {@code false} otherwise
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
*/
public boolean contains(int i) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
return qp[i] != -1;
}

/**
* Returns the number of keys on this priority queue.
*
* @return the number of keys on this priority queue
*/
public int size() {
return n;
}

/**
* Associates key with index {@code i}.
*
* @param  i an index
* @param  key the key to associate with index {@code i}
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if there already is an item associated
*         with index {@code i}
*/
public void insert(int i, Key key) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
n++;
qp[i] = n;
pq[n] = i;
keys[i] = key;
swim(n);
}

/**
* Returns an index associated with a minimum key.
*
* @return an index associated with a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public int minIndex() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}

/**
* Returns a minimum key.
*
* @return a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public Key minKey() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
return keys[pq[1]];
}

/**
* Removes a minimum key and returns its associated index.
* @return an index associated with a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public int delMin() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
int min = pq[1];
exch(1, n--);
sink(1);
assert min == pq[n+1];
qp[min] = -1;        // delete
keys[min] = null;    // to help with garbage collection
pq[n+1] = -1;        // not needed
return min;
}

/**
* Returns the key associated with index {@code i}.
*
* @param  i the index of the key to return
* @return the key associated with index {@code i}
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public Key keyOf(int i) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
else return keys[i];
}

/**
* Change the key associated with index {@code i} to the specified value.
*
* @param  i the index of the key to change
* @param  key change the key associated with index {@code i} to this key
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void changeKey(int i, Key key) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}

/**
* Change the key associated with index {@code i} to the specified value.
*
* @param  i the index of the key to change
* @param  key change the key associated with index {@code i} to this key
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @deprecated Replaced by {@code changeKey(int, Key)}.
*/
@Deprecated
public void change(int i, Key key) {
changeKey(i, key);
}

/**
* Decrease the key associated with index {@code i} to the specified value.
*
* @param  i the index of the key to decrease
* @param  key decrease the key associated with index {@code i} to this key
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if {@code key >= keyOf(i)}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void decreaseKey(int i, Key key) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) <= 0)
throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
keys[i] = key;
swim(qp[i]);
}

/**
* Increase the key associated with index {@code i} to the specified value.
*
* @param  i the index of the key to increase
* @param  key increase the key associated with index {@code i} to this key
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if {@code key <= keyOf(i)}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void increaseKey(int i, Key key) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) >= 0)
throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
keys[i] = key;
sink(qp[i]);
}

/**
* Remove the key associated with index {@code i}.
*
* @param  i the index of the key to remove
* @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void delete(int i) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, n--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}

/***************************************************************************
* General helper functions.
***************************************************************************/
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}

private void exch(int i, int j) {
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}

/***************************************************************************
* Heap helper functions.
***************************************************************************/
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}

/***************************************************************************
* Iterators.
***************************************************************************/

/**
* Returns an iterator that iterates over the keys on the
* priority queue in ascending order.
* The iterator doesn't implement {@code remove()} since it's optional.
*
* @return an iterator that iterates over the keys in ascending order
*/
public Iterator<Integer> iterator() { return new HeapIterator(); }

private class HeapIterator implements Iterator<Integer> {
// create a new pq
private IndexMinPQ<Key> copy;

// add all elements to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
copy = new IndexMinPQ<Key>(pq.length - 1);
for (int i = 1; i <= n; i++)
copy.insert(pq[i], keys[pq[i]]);
}

public boolean hasNext()  { return !copy.isEmpty();                     }
public void remove()      { throw new UnsupportedOperationException();  }

public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
}

}```

```static class Edge{
int from;
int to;
int dist;
int cost;

@Override
public String toString() {
return "{"+from + "->" + to + ", dist: " + dist + "}";
}
}

static int INF = 1 << 29;
static List<Edge>[] graph;
static int[] dist;
static int N;

@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
N = in.nextInt();
int M = in.nextInt();
if (N == 0 && M == 0) break;
graph = new ArrayList[N];
for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

for (int i = 0; i < M; ++i){
int f = in.nextInt();
int t = in.nextInt();
f--;
t--;
int dist = in.nextInt();
int cost = in.nextInt();

Edge edge = new Edge();
edge.from = f;
edge.to = t;
edge.cost = cost;
edge.dist = dist;

edge = new Edge();
edge.from = t;
edge.to = f;
edge.cost = cost;
edge.dist = dist;
}

dijkstra(0);
long sum = 0;
for (int i = 1; i < N; ++i){
int min = INF;
for (Edge e : graph[i]){
if (dist[i] == dist[e.to] + e.dist && e.cost < min){
min = e.cost;
}
}
sum += min;
}
System.out.println(sum);
}
}

static class Node implements Comparable<Node>{
int id;
int dist;
public Node(int id, int dist){
this.id = id;
this.dist = dist;
}

@Override
public int compareTo(Node o) {
return this.dist - o.dist;
}
}

private static void dijkstra(int s){
dist = new int[N];
Arrays.fill(dist,INF);
dist[s] = 0;
Queue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(s,dist[s]));
while (!pq.isEmpty()){
int v = pq.poll().id;
for (Edge e : graph[v]){
if (e.dist + dist[e.from] < dist[e.to]){
dist[e.to] = e.dist + dist[e.from];
pq.offer(new Node(e.to, dist[e.to]));
}
}
}
}```

## AOJ 2200: Mr. Rito Post Office

```dp[i][j] 表示快递分送到第i个城市时，小船在城市j的最短路径。

a. 小船的位置k == j,说明小船不需要移动，直接走陆地。
b. 小船的位置k != j,说明现在小船在其它城市，所以必须从i-1出发到城市k，在开船到j，把船停到j，再从陆地出发到i。

```static int[][] water;
static int[][] land;
static int N;
static int INF = 1 << 28;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
N = in.nextInt();
int M = in.nextInt();
if (N == 0 && M == 0) break;

water = new int[N][N];
land = new int[N][N];

for (int i = 0; i < N; ++i){
Arrays.fill(water[i], INF);
Arrays.fill(land[i],INF);
water[i][i] = 0;
land[i][i] = 0;
}

for (int i = 0; i < M; ++i){
int from = in.nextInt();
int to = in.nextInt();
from--;
to--;

int cost = in.nextInt();
String mark = in.next();
if (mark.equals("S")){
water[from][to] = water[to][from] = cost;
}
else{
land[from][to] = land[to][from] = cost;
}
}

int C = in.nextInt();
int[] city = new int[C];
for (int i = 0; i < C; ++i){
city[i] = in.nextInt() - 1;
}

warshallFloyd();

int[][] dp = new int[C][N];
for (int i = 0; i < C; ++i) Arrays.fill(dp[i], INF);
for (int i = 0; i < N; ++i){
dp[0][i] = land[city[0]][i] + water[i][city[0]];
}

for (int i = 1; i < C; ++i){
for (int j = 0; j < N; ++j){
for (int k = 0; k < N; ++k){
if (j != k){
dp[i][k] = Math.min(dp[i][k], dp[i-1][j] + land[city[i-1]][j] + water[j][k] + land[k][city[i]]);
}
else{
dp[i][k] = Math.min(dp[i][k], dp[i-1][j] + land[city[i-1]][city[i]]);
}
}
}
}

int min = INF;
for (int i = 0; i < N; ++i){
min = Math.min(min, dp[C-1][i]);
}

System.out.println(min);
}
}

private static void warshallFloyd(){
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
for (int k = 0; k < N; ++k){
water[j][k] = Math.min(water[j][k], water[j][i] + water[i][k]);
land[j][k] = Math.min(land[j][k], land[j][i] + land[i][k]);
}
}
}
}```

## POJ 3259: Wormholes

```static class Edge{
int from;
int to;
int cost;

public String toString(){
return from + "->" + to + " (" + cost + ")";
}
}

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int F = in.nextInt();
while (F-- != 0){
int V = in.nextInt();
int p = in.nextInt();
int w = in.nextInt();
Edge[] edges = new Edge[2 * p + w];
int E = 0;
for (int i = 0; i < p; ++i){
int from = in.nextInt();
int to = in.nextInt();
int cost = in.nextInt();
from--;
to--;

Edge edge = new Edge();
edge.from = from;
edge.to = to;
edge.cost = cost;
edges[E++] = edge;

edge = new Edge();
edge.from = to;
edge.to = from;
edge.cost = cost;
edges[E++] = edge;
}

for (int i = 0; i < w; ++i){
int from = in.nextInt();
int to = in.nextInt();
int cost = in.nextInt();
from--;
to--;
cost = -cost;

Edge edge = new Edge();
edge.from = from;
edge.to = to;
edge.cost = cost;
edges[E++] = edge;
}

System.out.println(findNegativeCycle(edges, V) ? "YES" : "NO");
}
}

static final int INF = 1 << 29;
private static boolean findNegativeCycle(Edge[] edges, int V){
int[] d = new int[V];
for (int i = 0; i < V; ++i){
for (Edge e : edges){
if(e.cost + d[e.from] < d[e.to]){
d[e.to] = e.cost + d[e.from];
if (i == V - 1) return true;
}
}
}
return false;
}```

346 篇文章47 人订阅

0 条评论