一、题目
大意：n个城市以及他们之间的m条路构成了图，每个城市驻有大小不同的救援队，你所在的城市为c1，当c2发生险情时，你需要带领c1城市的救援队按最短路径赶往c2，所经过城市的救援队也会加入你们。输入：n（城市数），m（路数），c1（你所在城市），c2（需要救援的城市）；每个城市驻扎救援队数目；m条路的起点、终点、长度。输出：最短路径的数目以及在这些路径中所能集合的救援队最大数目。
二、分析
在Dijkstra中，当一个顶点v加入到最短路径集合S中时，需要更新c1到其余未加入S顶点的距离，这时有三种情况（用Length[i]表示从c1到i的最短路径长度，用Graph[v][i]表示从v直接到j而不经过中间点的距离，RoadNum[i]表示从c1到i的最短路径数目，MaxRanks[i]表示在从c1到i的最短路径中能集合的最大救援队数目）： ①、Length[i]<Length[v]+Graph[v][i]，这种情况下最短路径还是Length[i]，不需做任何改动。 ②、Length[i]=Length[v]+Graph[v][i]，注意Length[i]此时还未更新，也就是说Length[i]表示的是在v还未加入S时，c1以S中某些点为中间点到i的距离，这条路径是不经过v的；而Length[v]+Graph[v][i]表示c1经过v到i的一条（或多条）路的长度，所以这两条（或多条）路是不会重合的。这个时候，从c1到i的最短路就是从c1不经过v到i的路（RoadNum[i])+经过v的路(RoadNum[v])；救援队数目选这些路里边最大的那个。 RoadNum[j]+=RoadNum[v]; MaxRanks[j]=(MaxRanks[v]+Weight[j])>MaxRanks[j]? (MaxRanks[v]+Weight[j]):MaxRanks[j]; ③、Length[i]>Length[v]+Graph[v][i]，这时候最短路径就是Length[v]+Graph[v][i]了，需要更新Length[i]。从c1到i就是从c1到v到i。 Length[j]=Length[v]+Graph[v][j]; MaxRanks[j]=MaxRanks[v]+Weight[j]; RoadNum[j]=RoadNum[v];
三、代码
#include <iostream>
#include <memory.h>
using namespace std
;
#define Maxnum 505
#define Infinity 1e8
int Graph
[Maxnum
][Maxnum
];
int Length
[Maxnum
];
int MaxRanks
[Maxnum
];
int RoadNum
[Maxnum
];
int Weight
[Maxnum
];
bool Final
[Maxnum
];
void Dijkstra(int n
)
{
for (int i
= 0; i
< n
; ++i
) {
int min
=Infinity
;
int v
=-1;
for (int j
= 0; j
< n
; ++j
) {
if(!Final
[j
]&&Length
[j
]<min
){
v
=j
;min
=Length
[j
];
}
}
if(v
==-1)break;
else
Final
[v
]=true;
for (int j
= 0; j
< n
; ++j
) {
if(!Final
[j
]&&(Length
[j
]==Length
[v
]+Graph
[v
][j
])){
RoadNum
[j
]+=RoadNum
[v
];
MaxRanks
[j
]=(MaxRanks
[v
]+Weight
[j
])>MaxRanks
[j
]?
(MaxRanks
[v
]+Weight
[j
]):MaxRanks
[j
];
}
else if(!Final
[j
]&&((Length
[j
]>Length
[v
]+Graph
[v
][j
]))){
Length
[j
]=Length
[v
]+Graph
[v
][j
];
MaxRanks
[j
]=MaxRanks
[v
]+Weight
[j
];
RoadNum
[j
]=RoadNum
[v
];
}
}
}
}
int main(){
fill(Graph
[0],Graph
[0]+Maxnum
*Maxnum
,Infinity
);
fill(Length
,Length
+Maxnum
,Infinity
);
fill(MaxRanks
,MaxRanks
+Maxnum
,0);
fill(RoadNum
,RoadNum
+Maxnum
,0);
memset(Final
, false, sizeof(Final
));
int n
,m
,c1
,c2
;
cin
>>n
>>m
>>c1
>>c2
;
for (int i
= 0; i
< n
; ++i
) cin
>>Weight
[i
];
for (int i
= 0; i
< m
; ++i
) {
int row
,col
,dist
;
cin
>>row
>>col
>>dist
;
Graph
[row
][col
]=Graph
[col
][row
]=dist
;
}
Length
[c1
]=0;
MaxRanks
[c1
]=Weight
[c1
];
RoadNum
[c1
]=1;
Dijkstra(n
);
cout
<<RoadNum
[c2
]<<" "<<MaxRanks
[c2
];
return 0;
}
二刷：用dijkstra+dfs做
#include<iostream>
#include<vector>
using namespace std
;
const int maxn
= 510;
const int inf
= 0x3fffffff;
int graph
[maxn
][maxn
], dis
[maxn
], weight
[maxn
], mark
[maxn
], n
, m
, start
, end1
, cnt
= 0, maxW
= 0;
vector
<vector
<int>>pre
;
vector
<int>temp
;
void dijkstra(int start
) {
dis
[start
] = 0;
for (int i
= 0; i
< n
; i
++) {
int pos
= -1, min
= inf
;
for (int j
= 0; j
< n
; j
++) {
if (mark
[j
] == 0 && dis
[j
] < min
) {
min
= dis
[j
];
pos
= j
;
}
}
if (pos
== -1)return;
mark
[pos
] = 1;
for (int j
= 0; j
< n
; j
++) {
if (mark
[j
] == 0) {
if (graph
[pos
][j
] + dis
[pos
] < dis
[j
]) {
pre
[j
].clear();
pre
[j
].push_back(pos
);
dis
[j
] = dis
[pos
] + graph
[pos
][j
];
}
else if (graph
[pos
][j
] + dis
[pos
] == dis
[j
])
pre
[j
].push_back(pos
);
}
}
}
}
void dfs(int e
) {
if (e
== start
) {
temp
.push_back(e
);
cnt
++;
int sumW
= 0;
for (int i
= 0; i
< temp
.size(); i
++)sumW
+= weight
[temp
[i
]];
maxW
= (maxW
> sumW
) ? maxW
: sumW
;
temp
.pop_back();
return;
}
temp
.push_back(e
);
for (int i
= 0; i
< pre
[e
].size(); i
++)dfs(pre
[e
][i
]);
temp
.pop_back();
}
int main() {
cin
>> n
>> m
>> start
>> end1
;
pre
.resize(n
);
for (int i
= 0; i
< n
; i
++) {
dis
[i
] = inf
;
mark
[i
] = 0;
for (int j
= 0; j
< n
; j
++) graph
[i
][j
] = inf
;
}
for (int i
= 0; i
< n
; i
++)cin
>> weight
[i
];
for (int i
= 0; i
< m
; i
++) {
int x
, y
, l
;
cin
>> x
>> y
>> l
;
graph
[x
][y
] = graph
[y
][x
] = l
;
}
dijkstra(start
);
dfs(end1
);
cout
<< cnt
<< " " << maxW
<< endl
;
return 0;
}
