Dijkstra算法扩展
解题代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define mt memset
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 510;
int N,M,S,D;
int mp[maxn][maxn],team[maxn],dis[maxn],cnt_team[maxn],cnt_road[maxn],pre[maxn];
//邻接矩阵，每个城市救援队数，源点到各点最短路，源点到各点最大救援队数，源点到各点最短路条数，父节点
bool vis[maxn];
void path(int x) {
if(x == -1)return ;
if(pre[x] != -1) {
path(pre[x]);
cout << " " << x;
}else {
cout << x;
}
}
void dijkstra() {
for(int i = 0; i < N; i++) {
dis[i] = mp[S][i];
vis[i] = false;
pre[i] = (i == S? -1: S);
if(i != S) {
if(dis[i] != inf) {
cnt_team[i] = team[S] + team[i];
}else {
cnt_team[i] = team[i];
}
}else {
cnt_team[i] = team[S];
}
cnt_road[i] = 1;
}
vis[S] = true;
for(int i = 1; i < N; i++) {
int _min = inf, pos = -1;
for(int j = 0; j < N; j++) {
if(!vis[j] && _min > dis[j]) {
_min = dis[j];
pos = j;
}
}
if(inf == _min || -1 == pos)continue;
vis[pos] = true;
for(int j = 0; j < N; j++) {
if(!vis[j]) {
if(dis[j] > dis[pos]+mp[pos][j]) {
dis[j] = dis[pos]+mp[pos][j];
cnt_road[j] = cnt_road[pos];
cnt_team[j] = cnt_team[pos]+team[j];
pre[j] = pos;
}else if(dis[j] == dis[pos]+mp[pos][j]) {
cnt_road[j] = cnt_road[j]+cnt_road[pos];
if(cnt_team[j] < cnt_team[pos]+team[j]) {
cnt_team[j] = cnt_team[pos]+team[j];
pre[j] = pos;
}
}
}
}
}
cout << cnt_road[D] << " " << cnt_team[D] << endl;
path(D);
cout << endl;
}
int main() {
while(~scanf("%d%d%d%d", &N, &M, &S, &D)) {
for(int i = 0; i < N; i++) {
scanf("%d", &team[i]);
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
mp[i][j] = (i == j?0:inf);
}
}
int u,v,w;
for(int i = 0; i < M; i++) {
scanf("%d%d%d", &u, &v, &w);
mp[u][v] = mp[v][u] = w;
}
dijkstra();
}
return 0;
}
总结
这道题目非常适合用来加深理解Dijkstra算法，其中用到的关于到达每个点的最短路路径数目的记录，与计算到达每个点的最大的救援队数目，利用了一些动态规划的思想，十分的巧妙。
之前打ACM的时候对模板的依赖太多，所以现在要慢慢对每种经典算法进行熟悉理解，争取做到能够手敲，而不是一味的复制粘贴模板。共勉。