Dijkstra算法_最短路径_L2-001. 紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式：

输入第一行给出4个正整数N、M、S、D，其中N（2<=N<=500）是城市的个数，顺便假设城市的编号为0~(N-1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式：

第一行输出不同的最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出首尾不能有多余空格。

输入样例：

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例：

2 60
0 1 3

这道题说白了就是寻找最短路径,但是由于pat平台很蠢，很蠢很蠢，对JAVA支持很差，跑一个syso都要100ms！这种算法题你要我200ms做完？
迫于无奈 用java和C分别实现了一边，效率不提了

这两个代码的核心思路是完全一样的，pat这个平台对于java，有的时候还需要用BufferedReader来接受，用scanner会超时，我真的是无话可说。

  1 import java.io.BufferedReader;
  2 import java.io.IOException;
  3 import java.io.InputStreamReader;
  4 import java.util.Arrays;
  5 
  6 public class Main {
  7 
  8     static int MAXVEX ;
  9     static int INFINITY = 65535;
 10     static int[] Pathmatirx;
 11     static int[] ShortPathTable;
 12     static int[][] graph;
 13     static int[] Spnum;
 14     static int[] nums;
 15     static int[] values;
 16     public static void main(String[] args) throws IOException {
 17         BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
 18         String[] string = bReader.readLine().split(" ");
 19         int n = Integer.parseInt(string[0]);
 20         int m = Integer.parseInt(string[1]);
 21         int s = Integer.parseInt(string[2]);
 22         int d = Integer.parseInt(string[3]);
 23         nums = new int[n];
 24         MAXVEX = n;
 25         Pathmatirx = new int[MAXVEX];
 26         ShortPathTable = new int[MAXVEX];
 27         graph = new int[MAXVEX][MAXVEX]; 
 28         Spnum = new int[MAXVEX];
 29         for (int i = 0; i < MAXVEX; i++) {
 30             Arrays.fill(graph[i], INFINITY);
 31             graph[i][i] = 0;
 32         }
 33         string = bReader.readLine().split(" ");
 34         for (int i = 0; i < n; i++) {
 35             nums[i] = Integer.parseInt(string[i]);
 36         }
 37         for (int i = 0; i < m; i++) {
 38             string = bReader.readLine().split(" ");
 39             int t1 = Integer.parseInt(string[0]);
 40             int t2 = Integer.parseInt(string[1]);
 41             int t3 = Integer.parseInt(string[2]);
 42             graph[t1][t2] = t3;
 43         }
 44         for (int i = 0; i < MAXVEX; i++) {
 45             for (int j = 0; j < MAXVEX; j++) {
 46                 if (graph[i][j]==INFINITY&&graph[j][i]!=INFINITY) {
 47                     graph[i][j] = graph[j][i];
 48                 }
 49             }
 50         }
 51         Dijkstra(s);
 52         System.out.print(Spnum[d]+" ");
 53         System.out.print(values[d]);
 54         System.out.println("");
 55         StringBuilder st = new StringBuilder(s+"");
 56         st.append(" "+d);
 57         while (Pathmatirx[d]!=0) {
 58           st.insert(1, " "+Pathmatirx[d]);
 59           d = Pathmatirx[d];
 60         }
 61         System.out.print(st.toString());
 62     }
 63     
 64     public static void Dijkstra(int v0) {
 65         int v,w,k = 0,min;
 66         values = new int[MAXVEX];
 67         int[] res = new int[MAXVEX];    //判断是否已经保存最短路径 
 68         for (int i = 0; i < MAXVEX; i++) {
 69             ShortPathTable[i] = graph[v0][i];
 70             if (i!=v0) {
 71                 values[i] = nums[i]+nums[v0];
 72             }
 73         }
 74         Arrays.fill(Spnum, 1);
 75         res[v0] = 1;//v0->v0 v0最短路径就是自己
 76         values[v0] = nums[v0];
 77         for (int i = 0; i < MAXVEX; i++) {
 78             if (i == v0) {
 79                 continue;
 80             }
 81             min = INFINITY;
 82             for (int j = 0; j < MAXVEX; j++) {
 83                 if (res[j]==0&&ShortPathTable[j]<min) { //最短路径还未找出 且权值最小
 84                     k = j;  //保存离i节点最近的节点
 85                     min = ShortPathTable[j];
 86                 }
 87                 
 88             }
 89             //这个循环结束后 暂时的最短路径保存下来 但是只有离i节点最近的节点加入了res
 90             res[k] = 1;
 91 
 92             for (int j = 0; j < MAXVEX; j++) {
 93                 //如果节点没有加入res 且现有的路径比之前找到过的小 就更新
 94                 //若节点未联通 graph[k][j]和ShorPath[j]都是65535
 95                 if (res[j] == 0&&(min+graph[k][j])<ShortPathTable[j]) {
 96                     ShortPathTable[j] = min+graph[k][j];
 97                     values[j] = values[k]+nums[j];
 98                     Spnum[j] = Spnum[k];
 99                     Pathmatirx[j] = k;
100                 }else if ((res[j] == 0&&(min+graph[k][j])==ShortPathTable[j])) {
101                     Spnum[j] +=Spnum[k];
102                     if (values[j]<values[k]+nums[j]) {
103                         values[j]=values[k]+nums[j];
104                         Pathmatirx[j] = k;  //这个要放在里面 若是又更好的路径 就更换前置节点
105                     }
106                 }
107 
108             }
109             
110         }
111         
112     }
113 }

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 int const MAX = 505;
  5 int const INF = 0x3fffffff;
  6 int graph[MAX][MAX], val[MAX], dis[MAX], totval[MAX], pathnum[MAX], path[MAX];
  7 bool vis[MAX];
  8 int n, m, s, d;
  9 
 10 void Dijkstra(int v0)
 11 {
 12     for (int i = 0; i < n; i++)
 13     {
 14         dis[i] = graph[v0][i];
 15         totval[i] = val[i] + val[v0];
 16         pathnum[i] = 1;
 17         vis[i] = false;
 18         path[i] = v0;
 19     }
 20     vis[v0] = true;
 21     totval[v0] = val[v0];
 22     for (int i = 0; i < n; i++)
 23     {
 24         if (i == v0)
 25         {
 26             continue;
 27         }
 28         int min = INF;
 29         int k = 0;
 30         for (int j = 0; j < n; j++)
 31         {
 32             if (vis[j] == false && min > dis[j])
 33             {
 34                 min = dis[j];
 35                 k = j;
 36             }
 37         }
 38         vis[k] = true;
 39         for (int i = 0; i < n; i++)
 40         {
 41             if (vis[i] == false)
 42             {
 43                 if (min + graph[k][i] < dis[i])
 44                 {
 45                     dis[i] = min + graph[k][i];
 46                     pathnum[i] = pathnum[k];
 47                     totval[i] = totval[k] + val[i];
 48                     path[i] = k;
 49                 }
 50                 else if (min + graph[k][i] == dis[i])
 51                 {
 52                     pathnum[i] += pathnum[k];
 53                     if (totval[i] < totval[k] + val[i])
 54                     {
 55                         totval[i] = totval[k] + val[i];
 56                         path[i] = k;
 57 
 58                     }
 59                 }
 60             }
 61         }
 62     }
 63 }
 64 
 65 int main()
 66 {
 67     scanf("%d %d %d %d", &n, &m, &s, &d);
 68     for (int i = 0; i < n; i++)
 69     {
 70         scanf("%d", &val[i]);
 71     }
 72     for (int i = 0; i < n; i++)
 73     {
 74         for (int j = 0; j < n; j++)
 75         {
 76             graph[i][j] = INF;
 77         }
 78         graph[i][i] = 0;
 79     }
 80     for (int i = 0; i < m; i++)
 81     {
 82         int t1, t2, t3;
 83         scanf("%d %d %d", &t1, &t2, &t3);
 84         graph[t1][t2] = t3;
 85         graph[t2][t1] = t3;
 86     }
 87     Dijkstra(s);
 88     printf("%d %d
", pathnum[d], totval[d]);
 89     int t = d;
 90     int index = 0;
 91     int res[MAX];
 92     while (t != s)
 93     {
 94         res[index++] = t;
 95         t = path[t];
 96     }
 97     res[index++] = s;
 98     for (int i = index - 1; i > 0; i--) {
 99         printf("%d ", res[i]);
100     }
101     printf("%d
", res[0]);
102 
103 }

以前一直想参加PAT,看上去那么的高大上,虽然每届只有千把人参加,但是现在看看这个比赛对于java的不友好,还是算了吧.