1003 Emergency Dijkstra

这题做的心很累，我用的还是 1018的思路做的，但是使用dfs 求最大人数对于某些有问题（现在也不知道错哪了），

看了别人的代码后才发现，其实完全不用这么麻烦，只需设置一个点的权重，一遍DJ（自创简称）下来，直接出答案

收获：

1.DJ不需要存储具体路径也能知道最短路径有几条：

在DJ外设置一个road【n】数组，初始为0；road【源】=1；//road表示，从源出发，到n的最短路径条数

在更新环节

for（）

{

　　if当dis[u] + e[u][v] < dis[v]

　　　　road【v】=road【u】；

　　else if当dis[u] + e[u][v] == dis[v]

　　　　road【v】=road【v】+road【u】；　　　　//通过U到V的路，加上不经过U到V的条数

}//每个road【i】就是从源到i的最短路径条数了

2.使用点权解决不需要输出路径的问题

我在某大神的DJ算法中更新dis的部分看到了这样一句话

for(int v = 0; v < n; v++) {//已经找到一个集合外的最小点 u，

if(visit[v] == false && e[u][v] != inf) { 《-------这一句判断，不加这一句就是正常的思路，//对于既不是集合内的点，从U出发又不可达的点就跳过，感觉没有必要

if(dis[u] + e[u][v] < dis[v]) {　　　　　　//因为这句判断本身已经要对所有输入都判断一次了

dis[v] = dis[u] + e[u][v];

}

我的部分正确代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 const int inf=999999;
 6 int e[500][500];
 7 int man[500]={0};
 8 int N,M,C1=0,C2;
 9 int a,b,c;
10 int num=0,most=0;//最短路径数，最大人数
11 vector<int> pre[501];
12 vector<int> path,tmppath;
13 void dfs(int x)//由于存的是到达x的最短路径的前一个点，所以从后往前走C2起步
14 {
15   tmppath.push_back(x);
16   if(x==C1)
17   {
18     num++;
19     a=0;
20     for(int i=tmppath.size()-1;i>=0;i--)//i初始化为路径上C1的下一个点
21     {
22       a+=man[i];
23     }
24     if(a>most)
25     {
26       path=tmppath;
27       most=a;
28     }
29   }
30   else
31   {
32     for(int i=0;i<pre[x].size();i++)
33     {
34       dfs(pre[x][i]);
35     }
36   }
37   tmppath.pop_back();
38 }
39 
40 
41 
42 
43 int main()
44 {
45   scanf("%d%d%d%d",&N,&M,&C1,&C2);
46   int dis[N];//DJ 距离
47   int mark[N];//DJ 标记
48   for(int i=0;i<N;i++)
49   {
50     for(int j=0;j<N;j++)
51       e[i][j]=inf;
52     dis[i]=inf;
53     scanf("%d",&man[i]);
54     mark[i]=0;
55 
56   }
57   for(int i=0;i<M;i++)
58   {
59     scanf("%d%d%d",&a,&b,&c);
60     e[a][b]=e[b][a]=c;
61 
62   }
63   dis[C1]=0;//DJ初始化
64   int now=C1,fast;
65   for(int i=0;i<N;i++)//每次加入一个点
66   {
67     fast=inf;
68     for(int j=0;j<N;j++)
69     {
70       if(dis[j]<fast&&mark[j]==0)//dis 小于当前发现的最小，并且没有被加入
71       {
72         now=j;
73         fast=dis[j];
74       }
75     }
76     if(fast==inf)break;//所有可达点都加入了
77     mark[now]=1;//加入该点
78     for(int j=0;j<N;j++)//用当前该点更新dis,并且更新pre
79     {
80       if(dis[now]+e[j][now]<dis[j])
81       {
82         dis[j]=dis[now]+e[j][now];
83         pre[j].clear();
84         pre[j].push_back(now);
85       }
86       else if(dis[now]+e[j][now]==dis[j])
87       {
88         pre[j].push_back(now);
89       }
90     }
91   }//DJ 结束,dis[C2],为最短距离
92   dfs(C2);//使用深搜 求出最短路径的条数 和 最大人数
93   printf("%d %d",num,most);
94 
95   return 0;
96 }

mycode

正确代码：

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int e[510][510], weight[510], dis[510], num[510], w[510];
bool visit[510];
const int inf = 99999999;
int main() {
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d", &weight[i]);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[a][b] = e[b][a] = c;
    }
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    num[v] = num[u];
                    w[v] = w[u] + weight[v];
                } else if(dis[u] + e[u][v] == dis[v]) {
                    num[v] = num[v] + num[u];
                    if(w[u] + weight[v] > w[v])
                        w[v] = w[u] + weight[v];
                }
            }
        }
    }
    printf("%d %d", num[c2], w[c2]);
    return 0;
}

right code