HDu2680(Choose the best route)
[java]package graph_ShortestPath;
//思路:构建反向图。
import java.util.*;
import java.io.*;
public class HDU2680 {
static int[][]map;
static int[]dist;
static int n;
public static void main(String[] args) throws IOException {
//Scanner sc = new Scanner(System.in);
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int m,s;
while(st.nextToken()!=StreamTokenizer.TT_EOF){
n = (int)st.nval;
st.nextToken();
m = (int)st.nval;
st.nextToken();
s = (int)st.nval;
map = new int[n+1][n+1];
for (int i = 1; i <= n; i++)
Arrays.fill(map[i], Integer.MAX_VALUE);
dist = new int[n+1];
for(int i = 0;i<m;i++){
st.nextToken();
int p = (int)st.nval;
st.nextToken();
int q = (int)st.nval;
st.nextToken();
int t = (int)st.nval;
if(t<map[q][p])
map[q][p] = t;//反向图。
}
st.nextToken();
int num =(int)st.nval;
int min = Integer.MAX_VALUE;
int[]arr = new int[num+1];
for(int i = 1;i<=num;i++){
st.nextToken();
arr[i] =(int)st.nval;
}
dijkstra(s);
for(int i = 1;i<=num;i++){
if(dist[arr[i]]<min)
min = dist[arr[i]];
}
if(min>=Integer.MAX_VALUE)System.out.println(-1);
else System.out.println(min);
}
}
private static void dijkstra(int ss) {
boolean[] p = new boolean[n+1];
for(int i = 1;i<=n;i++){
p[i] = false;
if(i!=ss)dist[i] = map[ss][i];
}
p[ss] = true;
dist[ss] = 0;
for(int i = 0;i<n-1;i++){
int min = Integer.MAX_VALUE;
int k = -1;
for(int j = 1;j<=n;j++){
if(!p[j] && dist[j]<min){
min = dist[j];
k = j;
}
}
if(k==-1)return;
p[k] = true;
for(int j = 1;j<=n;j++){
if(!p[j] && map[k][j]!=Integer.MAX_VALUE && dist[j] > dist[k] +map[k][j])
dist[j]=dist[k]+map[k][j];
}
}
}
}
补充:软件开发 , Java ,