柳婼の blog – 第194页 – 我不管，反正我最萌～

1072. Gas Station (30)-PAT甲级真题（Dijkstra）

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.

Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: N (<= 103), the total number of houses; M (<= 10), the total number of the candidate locations for the gas stations; K (<= 104), the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.

Then K lines follow, each describes a road in the format
P1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.

Output Specification:

For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output “No Solution”.

Sample Input 1:
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
Sample Output 1:
G1
2.0 3.3
Sample Input 2:
2 1 2 10
1 G1 9
2 G1 20
Sample Output 2:
No Solution

题目大意：从m个加油站里面选取1个站点，让他离居民区的最近的人最远，并且没有超出服务范围ds之内。如果有很多个最远的加油站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列加油站编号最小的那个
分析：
因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。所以我们就是对n+m个点进行Dijkstra计算最短路径。要求计算出1~m号加油站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围ds的距离，那么我们就舍弃这个加油站。取最最短的路径，这就是距离它最近的加油站mindis。如果mindis > ansdis，就是说找到了一个距离居民最小距离的加油站是更远的，那就选这个加油站，更新ansid为它的id。最后输出
对于加油站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。
Update：Github用户littlesevenmo在issue中提出需要添加输入判断，题目中并没有说明两点之间最多只有一条路。也就是说，有可能两点之间有多条路，因此需要添加判断，只存储距离最短的路。另外，也有可能会出现 G1 G1 9999这样的测试数据，因此，自身与自身之间的距离要初始化为0。完善后的代码如下：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
    fill(e[0], e[0] + 1020 * 1020, inf);
    for (int i = 0; i < 1020; i++) e[i][i] = 0;
    fill(dis, dis + 1020, inf);
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    string s, t;
    for (int i = 0; i < k; i++) {
        int tempdis;
        cin >> s >> t >> tempdis;
        int a, b;
        if (s[0] == 'G') {
            s = s.substr(1);
            a = n + stoi(s);
        } else {
            a = stoi(s);
        }
        if (t[0] == 'G') {
            t = t.substr(1);
            b = n + stoi(t);
        } else {
            b = stoi(t);
        }
        e[a][b] = e[b][a] = min(tempdis, e[a][b]);
    }
    int ansid = -1;
    double ansdis = -1, ansaver = inf;
    for (int index = n + 1; index <= n + m; index++) {
        double mindis = inf, aver = 0;
        fill(dis, dis + 1020, inf);
        fill(visit, visit + 1020, false);
        dis[index] = 0;
        for (int i = 0; i < n + m; i++) {
            int u = -1, minn = inf;
            for (int j = 1; j <= n + m; j++) {
                if (visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if (u == -1) break;
            visit[u] = true;
            for (int v = 1; v <= n + m; v++) {
                if (visit[v] == false && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (dis[i] > ds) {
                mindis = -1;
                break;
            }
            if (dis[i] < mindis) mindis = dis[i];
            aver += 1.0 * dis[i];
        }
        if (mindis == -1) continue;
        aver = aver / n;
        if (mindis > ansdis) {
            ansid = index;
            ansdis = mindis;
            ansaver = aver;
        } else if (mindis == ansdis && aver < ansaver) {
            ansid = index;
            ansaver = aver;
        }
    }
    if (ansid == -1)
        printf("No Solution");
    else
        printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

const int inf = 999999999;

int n, m, k, ds, station;

int e[1020][1020], dis[1020];

bool visit[1020];

int main() {

fill(e[0], e[0] + 1020 * 1020, inf);

for (int i = 0; i < 1020; i++) e[i][i] = 0;

fill(dis, dis + 1020, inf);

scanf("%d%d%d%d", &n, &m, &k, &ds);

string s, t;

for (int i = 0; i < k; i++) {

int tempdis;

cin >> s >> t >> tempdis;

int a, b;

if (s[0] == 'G') {

s = s.substr(1);

a = n + stoi(s);

} else {

a = stoi(s);

}

if (t[0] == 'G') {

t = t.substr(1);

b = n + stoi(t);

} else {

b = stoi(t);

}

e[a][b] = e[b][a] = min(tempdis, e[a][b]);

}

int ansid = -1;

double ansdis = -1, ansaver = inf;

for (int index = n + 1; index <= n + m; index++) {

double mindis = inf, aver = 0;

fill(dis, dis + 1020, inf);

fill(visit, visit + 1020, false);

dis[index] = 0;

for (int i = 0; i < n + m; i++) {

int u = -1, minn = inf;

for (int j = 1; j <= n + m; j++) {

if (visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if (u == -1) break;

visit[u] = true;

for (int v = 1; v <= n + m; v++) {

if (visit[v] == false && dis[v] > dis[u] + e[u][v])

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

}

for (int i = 1; i <= n; i++) {

if (dis[i] > ds) {

mindis = -1;

break;

}

if (dis[i] < mindis) mindis = dis[i];

aver += 1.0 * dis[i];

}

if (mindis == -1) continue;

aver = aver / n;

if (mindis > ansdis) {

ansid = index;

ansdis = mindis;

ansaver = aver;

} else if (mindis == ansdis && aver < ansaver) {

ansid = index;

ansaver = aver;

}

if (ansid == -1)

printf("No Solution");

else

printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);

return 0;

}

1030. Travel Plan (30)-PAT甲级真题（Dijkstra + DFS，输出路径，边权）

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output
0 2 3 3 40
题目大意：求起点到终点的最短路径最短距离和花费，要求首先路径最短，其次花费最少，要输出完整路径
分析：Dijksta + DFS。 Dijkstra记录路径pre数组，然后用dfs求最短的一条mincost以及它的路径path，最后输出path数组和mincost
注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, s, d;
int e[510][510], dis[510], cost[510][510];
vector<int> pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v) {
    temppath.push_back(v);
    if(v == s) {
        int tempcost = 0;
        for(int i = temppath.size() - 1; i > 0; i--) {
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += cost[id][nextid];
        }
        if(tempcost < mincost) {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &n, &m, &s, &d);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
        scanf("%d", &cost[a][b]);
        cost[b][a] = cost[a][b];
    }
    pre[s].push_back(s);
    dis[s] = 0;
    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[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(d);
    for(int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);
    printf("%d %d", dis[d], mincost);
    return 0;
}

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

int n, m, s, d;

int e[510][510], dis[510], cost[510][510];

vector<int> pre[510];

bool visit[510];

const int inf = 99999999;

vector<int> path, temppath;

int mincost = inf;

void dfs(int v) {

temppath.push_back(v);

if(v == s) {

int tempcost = 0;

for(int i = temppath.size() - 1; i > 0; i--) {

int id = temppath[i], nextid = temppath[i-1];

tempcost += cost[id][nextid];

}

if(tempcost < mincost) {

mincost = tempcost;

path = temppath;

}

temppath.pop_back();

return ;

}

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

scanf("%d%d%d%d", &n, &m, &s, &d);

for(int i = 0; i < m; i++) {

int a, b;

scanf("%d%d", &a, &b);

scanf("%d", &e[a][b]);

e[b][a] = e[a][b];

scanf("%d", &cost[a][b]);

cost[b][a] = cost[a][b];

}

pre[s].push_back(s);

dis[s] = 0;

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[v] > dis[u] + e[u][v]) {

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

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

dfs(d);

for(int i = path.size() - 1; i >= 0; i--)

printf("%d ", path[i]);

printf("%d %d", dis[d], mincost);

return 0;

}

L2-013. 红色警报-PAT团体程序设计天梯赛GPLT（图的连通分量个数统计）

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

输入格式：

输入在第一行给出两个整数N（0 < N <=500）和M（<=5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。

注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出格式：

对每个被攻占的城市，如果它会改变整个国家的连通性，则输出“Red Alert: City k is lost!”，其中k是该城市的编号；否则只输出“City k is lost.”即可。如果该国失去了最后一个城市，则增加一行输出“Game Over.”。

输入样例：
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
分析：用图的深度优先遍历判断一个图内的连通分量有多少个，标记为cnt，之后对于每一个输入数据，因为城市a被攻占，所以把a的所有路径标注为不可达(0)，再统计连通分量的个数tempcnt，如果tempcnt > cnt + 1，也就是说当现在的连通分量多余以前的连通分量+1的时候，说明改变了图的连通性；（因为城市被攻占本身它城市自己就变成了一个单独的城市，多出来一个连通分量，只要tempcint <= cnt + 1都说明没有改变图的连通性），每一次tempcnt在用完之后把cnt的值更新为tempcnt，保证下一次的判断是建立再已经失去之前这么多城市的基础之上的。
因为题目中说输入保证给出的被攻占的城市编号都是合法的且无重复，所以如果城市失去了n个，就是当前输入的是从0开始的第n-1个数据的时候，就说明Game Over了，最后当if(i == n – 1) printf(“Game Over.\n”);

#include <cstdio>
#include <algorithm>
using namespace std;
bool visit[510];
int e[510][510], n, m, k;
void dfs(int node) {
    visit[node] = true;
    for(int i = 0; i < n; i++) {
        if(visit[i] == false && e[node][i] == 1)
            dfs(i);
    }
}
int countcnt() {
    int cnt = 0;
    fill(visit, visit + 510, false);
    for(int i = 0; i < n; i++) {
        if(visit[i] == false) {
            dfs(i);
            cnt++;
        }
    }
    return cnt;
}
int main() {
    scanf("%d%d", &n, &m);
    int a, b, city;
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        e[a][b] = e[b][a] = 1;
    }
    int cnt = countcnt();
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        scanf("%d", &city);
        for(int j = 0; j < n; j++) {
            if(e[city][j] == 1) {
                e[city][j] = 0;
                e[j][city] = 0;
            }
        }
        int tempcnt = countcnt();
        if(tempcnt > cnt + 1)
            printf("Red Alert: City %d is lost!\n", city);
        else
            printf("City %d is lost.\n", city);
        cnt = tempcnt;
        if(i == n - 1) printf("Game Over.\n");
    }
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

bool visit[510];

int e[510][510], n, m, k;

void dfs(int node) {

visit[node] = true;

for(int i = 0; i < n; i++) {

if(visit[i] == false && e[node][i] == 1)

dfs(i);

}

int countcnt() {

int cnt = 0;

fill(visit, visit + 510, false);

for(int i = 0; i < n; i++) {

if(visit[i] == false) {

dfs(i);

cnt++;

}

return cnt;

}

int main() {

scanf("%d%d", &n, &m);

int a, b, city;

for(int i = 0; i < m; i++) {

scanf("%d%d", &a, &b);

e[a][b] = e[b][a] = 1;

}

int cnt = countcnt();

scanf("%d", &k);

for(int i = 0; i < k; i++) {

scanf("%d", &city);

for(int j = 0; j < n; j++) {

if(e[city][j] == 1) {

e[city][j] = 0;

e[j][city] = 0;

}

int tempcnt = countcnt();

if(tempcnt > cnt + 1)

printf("Red Alert: City %d is lost!\n", city);

else

printf("City %d is lost.\n", city);

cnt = tempcnt;

if(i == n - 1) printf("Game Over.\n");

}

return 0;

}

L2-001. 紧急救援-PAT团体程序设计天梯赛GPLT（Dijkstra算法）

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

输入格式：

输入第一行给出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
分析：用一遍dijkstra算法。设立num[i]和w[i]表示从出发点到i结点拥有的路的条数，以及能够找到的救援队的数目～～当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];
再设立一个pre[i]表示最短路径的前一个结点，在dis[u] + e[u][v] <= dis[v]的时候更新pre[v] = u，最后递归打印路径即可

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int dis[510], weight[510], e[510][510], num[510], w[510], pre[510];
bool visit[510];
const int inf = 99999999;
void printPath(int v) {
    if(v == c1) {
        printf("%d", v);
        return ;
    }
    printPath(pre[v]);
    printf(" %d", v);
}
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] = c;
        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];
                    pre[v] = u;
                } 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];
                        pre[v] = u;
                    }
                }
            }
        }
    }
    printf("%d %d\n", num[c2], w[c2]);
    printPath(c2);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

int n, m, c1, c2;

int dis[510], weight[510], e[510][510], num[510], w[510], pre[510];

bool visit[510];

const int inf = 99999999;

void printPath(int v) {

if(v == c1) {

printf("%d", v);

return ;

}

printPath(pre[v]);

printf(" %d", v);

}

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] = c;

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];

pre[v] = u;

} 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];

pre[v] = u;

}

printf("%d %d\n", num[c2], w[c2]);

printPath(c2);

return 0;

}

1003. Emergency (25)-PAT甲级真题（Dijkstra算法）

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) – the number of cities (and the cities are numbered from 0 to N-1), M – the number of roads, C1 and C2 – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output

2 4

题目大意：n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个～

分析：用一遍Dijkstra算法～救援小组个数相当于点权，用Dijkstra求边权最小的最短路径的条数，以及这些最短路径中点权最大的值～dis[i]表示从出发点到i结点最短路径的路径长度，num[i]表示从出发点到i结点最短路径的条数，w[i]表示从出发点到i点救援队的数目之和～当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];

#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;
}

#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;

}

【最短路径】之Dijkstra算法

最短路径

单源最短路径：计算源点到其他各顶点的最短路径的长度
全局最短路径：图中任意两点的最短路径
Dijkstra、Bellman-Ford、SPFA求单源最短路径
Floyed可以求全局最短路径，但是效率比较低
SPFA算法是Bellman-Ford算法的队列优化
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。
深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

Dijkstra() {
  初始化;
  for(循环n次) {
    u = 使dis[u]最小的还未被访问的顶点的编号;
    记u为确定值;
    for(从u出发能到达的所有顶点v){
      if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)
        优化dis[v];
    }
  }
}

Dijkstra() {

初始化;

for(循环n次) {

u = 使dis[u]最小的还未被访问的顶点的编号;

记u为确定值;

for(从u出发能到达的所有顶点v){

if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)

优化dis[v];

}

//邻接矩阵
int n, e[maxv][maxv];
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
  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) return;
    visit[u] = true;
    for(int v = 0; v < n; v++) {
      if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {
        dis[v] = dis[u] + e[u][v];
        pre[v] = u; // pre用来标注当前结点的前一个结点
      }
    }
  }
}

//邻接矩阵

int n, e[maxv][maxv];

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool vis[maxv] = {false};

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

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) return;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {

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

pre[v] = u; // pre用来标注当前结点的前一个结点

}

//邻接表
struct node {
  int v, dis;
}
vector<node> e[maxv];
int n;
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool visit[maxv] = {false};
for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  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) return ;
    visit[u] = true;
    for(int j = 0; j < e[u].size(); j++) {
      int v = e[u][j].v;
      if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {
        dis[v] = dis[u] + e[u][j].dis;
        pre[v] = u;
      }
    }
  }
}

//邻接表

struct node {

int v, dis;

}

vector<node> e[maxv];

int n;

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool visit[maxv] = {false};

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

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) return ;

visit[u] = true;

for(int j = 0; j < e[u].size(); j++) {

int v = e[u][j].v;

if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {

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

pre[v] = u;

}

void dfs(int s, int v) {
  if(v == s) {
    printf("%d\n", s);
    return ;
  }
  dfs(s, pre[v]);
  printf("%d\n", v);
}

void dfs(int s, int v) {

if(v == s) {

printf("%d\n", s);

return ;

}

dfs(s, pre[v]);

printf("%d\n", v);

}

三种附加考法：第一标尺是距离，如果距离相等的时候，新增第二标尺

新增边权（第二标尺），要求在最短路径有多条时要求路径上的花费之和最小

for(int v = 0; v < n; v++) { //重写v的for循环
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      c[v] = c[u] + cost[u][v];
    }else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {
      c[v] = c[u] + cost[u][v];
    }
  }
}

for(int v = 0; v < n; v++) { //重写v的for循环

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

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

c[v] = c[u] + cost[u][v];

}else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {

c[v] = c[u] + cost[u][v];

}

给定每个点的点权（第二标尺），要求在最短路径上有多条时要求路径上的点权之和最大

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];
      w[v] = w[u] + weight[v];
    }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {
      w[v] = w[u] + weight[v];
    }
  }
}

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];

w[v] = w[u] + weight[v];

}else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

}

直接问有多少条最短路径

增加一个数组num[]，num[s] = 1，其余num[u] = 0，表示从起点s到达顶点u的最短路径的条数为num[u]

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[u] = num[v];
    }else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
    }
  }
}

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[u] = num[v];

}else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

}

例子：比如说又要路径最短，又要点权权值最大，而且还要输出个数，而且还要输出路径

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];
      pre[v] = u;
    } 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];
        pre[v] = u;
      }
    }
  }
}

void printPath(int v) {
    if(v == s) {
        printf("%d", v);
        return ;
    }
    printPath(pre[v]);
    printf("%d ", v);
}

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];

pre[v] = u;

} 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];

pre[v] = u;

}

void printPath(int v) {

if(v == s) {

printf("%d", v);

return ;

}

printPath(pre[v]);

printf("%d ", v);

}

of course, 可以不用这么麻烦，用Dijkstra求最短路径和pre数组，然后用深度优先遍历来获取想知道的一切，包括点权最大，边权最大，路径个数，路径
因为可能有多条路径，所以Dijkstra部分的pre数组使用vector<int> pre[maxv];

//Dijkstra部分
if(dis[u] + e[u][v] < dis[v]) {
  dis[v] = dis[u] + e[u][v];
  pre[v].clear();
  pre[v].push_back(u);
} else if(dis[i] + e[u] == dis[v]) {
  pre[v].push_back(u);
}

//Dijkstra部分

if(dis[u] + e[u][v] < dis[v]) {

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

pre[v].clear();

pre[v].push_back(u);

} else if(dis[i] + e[u] == dis[v]) {

pre[v].push_back(u);

}

既然已经求得pre数组，就知道了所有的最短路径，然后要做的就是用dfs遍历所有最短路径，找出一条使第二标尺最优的路径

int optvalue;
vector<int> pre[maxv];
vector<int> path, temppath;
void dfs(int v) { // v为当前访问结点
  if(v == start) {
    temppath.push_back(v);
    int value = 路径temppath上的value值;
    if(value 优于 optvalue) {
      optvalue = value;
      path = temppath;
    }
    temppath.pop_back();
    return ;
  }
  temppath.push_back(v);
  for(int i = 0; i < pre[v].size(); i++)
    dfs(pre[v][i]);
  temppath.pop_back();
}

int optvalue;

vector<int> pre[maxv];

vector<int> path, temppath;

void dfs(int v) { // v为当前访问结点

if(v == start) {

temppath.push_back(v);

int value = 路径temppath上的value值;

if(value 优于 optvalue) {

optvalue = value;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

解释：
- 对于递归边界而言，如果当前访问的结点是叶子结点（就是路径的开始结点），那么说明到达了递归边界，把v压入temppath，temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值，就path = temppath，然后把temppath的最后一个结点弹出，return ;
- 对于递归式而言，每一次都是把当前访问的结点压入，然后找他的pre[v][i]，进行递归，递归完毕后弹出最后一个结点
计算当前temppath边权或者点权之和的代码：

// 边权之和
int value = 0;
for(int i = tempptah.size() - 1; i > 0; i--) {
  int id = temppath[i], idnext = temppath[i - 1];
  value += v[id][idnext];
}
// 点权之和
int value = 0;
for(int i = temppath.size(); i >= 0; i--) {
  int id = temppath[i];
  value += w[id];
}

// 边权之和

int value = 0;

for(int i = tempptah.size() - 1; i > 0; i--) {

int id = temppath[i], idnext = temppath[i - 1];

value += v[id][idnext];

}

// 点权之和

int value = 0;

for(int i = temppath.size(); i >= 0; i--) {

int id = temppath[i];

value += w[id];

}

计算路径直接在Dijkstra部分写就可以
例子：计算最短距离的路径和最小花费

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, s, d;
int e[510][510], dis[510], cost[510][510];
vector<int> pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v) {
    if(v == s) {
        temppath.push_back(v);
        int tempcost = 0;
        for(int i = temppath.size() - 1; i > 0; i--) {
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += cost[id][nextid];
        }
        if(tempcost < mincost) {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &n, &m, &s, &d);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
        scanf("%d", &cost[a][b]);
        cost[b][a] = cost[a][b];
    }
    pre[s].push_back(s);
    dis[s] = 0;
    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 = 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[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(d);
    for(int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);
    printf("%d %d", dis[d], mincost);
    return 0;
}
//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

int n, m, s, d;

int e[510][510], dis[510], cost[510][510];

vector<int> pre[510];

bool visit[510];

const int inf = 99999999;

vector<int> path, temppath;

int mincost = inf;

void dfs(int v) {

if(v == s) {

temppath.push_back(v);

int tempcost = 0;

for(int i = temppath.size() - 1; i > 0; i--) {

int id = temppath[i], nextid = temppath[i-1];

tempcost += cost[id][nextid];

}

if(tempcost < mincost) {

mincost = tempcost;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

scanf("%d%d%d%d", &n, &m, &s, &d);

for(int i = 0; i < m; i++) {

int a, b;

scanf("%d%d", &a, &b);

scanf("%d", &e[a][b]);

e[b][a] = e[a][b];

scanf("%d", &cost[a][b]);

cost[b][a] = cost[a][b];

}

pre[s].push_back(s);

dis[s] = 0;

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 = 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[v] > dis[u] + e[u][v]) {

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

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

dfs(d);

for(int i = path.size() - 1; i >= 0; i--)

printf("%d ", path[i]);

printf("%d %d", dis[d], mincost);

return 0;

}

//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出