本文共 1979 字，大约阅读时间需要 6 分钟。
5-12 城市间紧急救援 (25分)
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数NN、MM、SS、DD，其中NN（2\le N\le 5002≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N-1)(N−1)；MM是快速道路的条数；SS是出发地的城市编号；DD是目的地的城市编号。
第二行给出NN个正整数，其中第ii个数是第ii个城市的救援队的数目，数字间以空格分隔。随后的MM行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的长度和和能够召集的最多的救援队数量。第二行输出从SS到DD的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 320 30 40 100 1 11 3 20 3 30 2 22 3 2
输出样例:
2 600 1 3
这是一道最短路基础上求最短路径长度和点权和最大值的问题,同时要记录最短路径.
运用迪杰斯特算法求出最短路,在做松弛时,由于要记录最短路径长度,所以当dis[i]=dis[j]+map[i][j]时,说明存在另外的路径让当前点到起点的距离最小,需要把pathnum[j](到达j点的最短路径长度,下同)加到pathnum[i]上.
用toval数组记录当前点满足最短路前提下的点权和的最大值,每次松弛操作都要更新,当dis[i]=dis[j]+map[i][j]时,判断total[j]+b[j](当前点的权值)是否大于total[i],如果大于就需要更新. 用pre数组作前缀数组,在每次松弛操作和dis[i]=dis[j]+map[i][j]相等时更新.
代码:
#include #include #include #include using namespace std;int n, m, s,q;int b[600];int a[600][600];int c[600];int pre[600];int inf;int sx[600];int toval[600];int main(){ memset(a, 0, sizeof(0)); int pathnum[600]; inf=99999999; scanf("%d%d%d%d", &n, &m, &s, &q); int i; int j; for(i=0; i c[j]) { mini=j; minn=c[j]; } } vis[mini]=1; for(j=0; j =0; top--) { printf("%d", sx[top]); if(top!=0)printf(" "); } return 0;}
spfa做法：
tot数组记录到达这个点的城市数量，注意当dis[x]+w==dis[y]的时候，tot[y]+=tot[x]，而不是tot[y]++
#include #define ps push_backusing namespace std;struct node{ int to; int w;};const int inf=1e9+7;vector edg[505];int dis[505], st[505], n;int num[505];int from[505];int tot[505];int book[505];int que[10000005];int m, s, d;void init(){ for(int i=0; i >n>>m>>s>>d; for(int i=0; i =0; i--)printf(i==0?"%d\n":"%d ", path[i]); return 0;}
转载地址：http://ziywb.baihongyu.com/