成语接龙(Idiomatic Phrases Game)

Idiomatic Phrases Game

Problem Description

  
  

   
   5
5 12345978ABCD2341
5 23415608ACBD3412
7 34125678AEFD4123
15 23415673ACC34123
4 41235673FBCD2156
2
20 12345678ABCD
30 DCBF5432167D
0
  
  
  

  
  

   
   17
-1
  
  
  

成语接龙 分数:5

       这道题用到了图的知识与Dijkstra算法（单源最短路径）。

       在这里附上来自于 海 子 的Dijkstra算法分析：点击打开链接

用java语言编写程序，代码如下：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while(input.hasNext()) {
			int n = input.nextInt();
			if(n == 0) break;
			
			int[] w = new int[n];
			String[] str = new String[n];
			
			for(int i = 0; i < n; i++) {
				w[i] = input.nextInt();
				str[i] = input.next();
			}
			
			//创建图——将字符串看成是顶点，而顶点的值是它所处的位置，而边则是两个能够匹配的字符串构成的“边”，
			//边的权值则是从第一个字符串到另一个匹配字符串的时间
			//g[i][j]表示从顶点i到顶点j所构成的边的权值，如果顶点i不能构成边，则权值赋值为最大值。
			int[][] g = new int[n][n];
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++) {
					int len = str[i].length();
					if(str[j].charAt(0) == str[i].charAt(len - 4) &&
							str[j].charAt(1) == str[i].charAt(len - 3) &&
							str[j].charAt(2) == str[i].charAt(len - 2) &&
							str[j].charAt(3) == str[i].charAt(len - 1))
						g[i][j] = w[i];
					else
						g[i][j] = Integer.MAX_VALUE;
				}
			
			int[] dist = new int[n];
			//单源最短路径算法
			Dijkstra(n, g, dist);
			if(dist[n - 1] != Integer.MAX_VALUE)
				System.out.println(dist[n - 1]);
			else
				System.out.println(-1);
		}
	}
	
	public static void Dijkstra(int n, int[][] g, int[] dist) {
		boolean[] isVisited = new boolean[n];
		for(int i = 0; i < n; i++)
			dist[i] = g[0][i];
		dist[0] = 0;
		isVisited[0] = true;
		for(int i = 1; i < n; i++) {
			int min = Integer.MAX_VALUE;
			int u = 0;
			for(int j = 0; j < n; j++) {
				if(dist[j] < min && !isVisited[j]) {
					min = dist[j];
					u = j;
				}
			}
			
			isVisited[u] = true;
			for(int j = 0; j < n; j++) {
				if(g[u][j] != Integer.MAX_VALUE && dist[u] + g[u][j] < dist[j] && !isVisited[j])
					dist[j] = dist[u] + g[u][j];
			}
		}
	}
}

另外这里还有一种时间超限的答案：（其中，同样是运用到了Dijkstra算法，只是实现不同罢了）

用java语言编写程序，代码如下：

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
//1124:成语接龙(时间超限)——Dijkstra最短路径

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		while(input.hasNext()) {
			int n = input.nextInt();
			if(n == 0) break;
			
			int source = 0, end = 0;
			boolean[] isExist = new boolean[70000];
			int numberOfVertices = 0;
			
			PriorityQueue<WeightEdge>[] q = new PriorityQueue[70000];
			for(int i = 0; i < n; i++) {
				int t = input.nextInt();
				String s = input.next();
				int u = Integer.valueOf(s.substring(0, 4), 16);
				int v = Integer.valueOf(s.substring(s.length() - 4, s.length()), 16);
				WeightEdge edge = new WeightEdge(u, v, t);
				
				if(i == 0)
					source = u;
				if(i == n - 1)
					end = u;
				
				if(isExist[u] == false) {
					isExist[u] = true;
					numberOfVertices++;
				}
				
				if(q[u] == null) {
					q[u] = new PriorityQueue<WeightEdge>();
				}
				q[u].add(edge);
			}
			
			if(n == 1) {
				System.out.println(0);
				continue;
			}
			int[] dist = new int[70000];
			getShortestPath(source, end, numberOfVertices, dist, q);
			if(dist[end] == Integer.MAX_VALUE)
				System.out.println(-1);
			else
				System.out.println(dist[end]);
		}
	}
	
	static class WeightEdge implements Comparable<WeightEdge> {
		int u, v, weight;
		public WeightEdge(int u, int v, int weight) {
			this.u = u;
			this.v = v;
			this.weight = weight;
		}
		
		public int compareTo(WeightEdge o) {
			return (weight - o.weight);
		}
	}
	
	public static void getShortestPath(int sourceIndex, int end, int numberOfVertices,
			int[] dist, PriorityQueue<WeightEdge>[] queues) {
		List<Integer> T = new ArrayList<Integer>();
		T.add(sourceIndex);
		
		for(int i = 0; i < dist.length; i++)
			dist[i] = Integer.MAX_VALUE;
		dist[sourceIndex] = 0;
		
		while(T.size() < numberOfVertices) {
			int v = -1;
			int smallestDist = Integer.MAX_VALUE;
			for(int u : T) {
				if(queues[u] == null)
					continue;
				
				while(!queues[u].isEmpty() && T.contains(queues[u].peek().v))
					queues[u].remove();
				
				if(queues[u].isEmpty())
					continue;
				
				WeightEdge e = queues[u].peek();
				if(dist[u] + e.weight < smallestDist) {
					v = e.v;
					smallestDist = dist[u] + e.weight;
				}
			}
			
			if(v != -1) {
				T.add(v);
				dist[v] = smallestDist;			
				if(v == end)
					return;
			}
		}
	}
}