PAT-GPLT训练集 L2-001 紧急救援(最短路)

PAT-GPLT训练集 L2-001 紧急救援

题目大意:求最短路的条数,最短路中的权重和的最大值和这条最短路的路线

分析:使用dijkstra算法求出最短路,并且对dijkstra算法进行变化,设起点为s,数量num[MAX_N],权重w[MAX_N],路径path[MAX_N];

   当d[i] > d[k] + es[k][i]时,说明这是一条k到i更短的路,那么这时需要进行操作:num[i] = num[k]; w[i] = w[k] + weight[i]; path[i] = k;

   当d[i] == d[k] + es[k][i]时,说明这又是一条到i结点的最短路,那么num[i] += num[k]; 那么这时需要考虑权重的大小,选择权重和更大的一条最短路,并修改path和权重w

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = ;
const int MAX_N = +;
int es[MAX_N][MAX_N];
int weight[MAX_N];
int d[MAX_N];
bool used[MAX_N];
int path[MAX_N];
int w[MAX_N];
int num[MAX_N];
int V, E, S, D;
void dijkstra() {
fill(d, d + V, INF);
fill(used, used + V, false);
d[S] = ;
num[S] = ;
w[S] = weight[S];
while() {
int k = -;
for(int i = ; i < V; i++) {
if(!used[i] && (k == - || d[k] > d[i])) k = i;
}
if(k == -) break;
used[k] = true;
for(int i = ; i < V; i++) {
if(d[k] + es[k][i] < d[i]) {
d[i] = d[k] + es[k][i];
num[i] = num[k];
path[i] = k;
w[i] = w[k] + weight[i];
}
else if(d[k] + es[k][i] == d[i]) {
num[i] += num[k];
if(w[i] < w[k] + weight[i]) {
w[i] = w[k] + weight[i];
path[i] = k;
}
}
}
}
}
void get_path(int D) {
if(D == S) {
printf("%d", S);
return;
}
get_path(path[D]);
printf(" %d", D);
}
int main() {
cin >> V >> E >> S >> D;
for(int i = ; i < V; i++) {
for(int j = ; j < V; j++) {
es[i][j] = INF;
}
}
for(int i = ; i < V; i++) cin >> weight[i];
int a, b, len;
for(int i = ; i < E; i++) {
cin >> a >> b >> len;
es[a][b] = es[b][a] = len;
}
dijkstra();
printf("%d %d\n", num[D], w[D]);
get_path(D);
return ;
}
上一篇:http://blog.csdn.net/czmchen/article/details/42392985


下一篇:097 Interleaving String 交错字符串