一.题目
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 Specification:
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 Specification:
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
二.题目思路
本题所考察为Dijkstra算法,第一行中所给的四个数分别为城市的个数,路的条数,当前的位置,需要救援的位置.第二行中的数为没一个城市中救援的人数.接下来的n行为起点+终点+路径长度.需要给出地点和重点之间的路的条数+能够集结的最多的救援人数
救援小组的个数相当与权值,dist数组用于表示从出发点到i节点最短路径的路径长度,num数组表示从出发点到i结点最短路径的条数,w数组表示从出发点到i点救援队的数目之和
三.代码
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
//a为城市个数,b为路的条数,c为起点,d为终点
int edge[501][501],wei[501],dis[501],num[501],w[501];
//edge为表示边集,wei为表示当下城市救援人数,dis为表示从出发点到当前点的最短路径的长度,num为出发点到当前点的最短路径的条数,w为从出发点到当前节点救援队的数目之和
bool visit[501];
//访问数组
const int inf=99999999;
//设置最大值
int main(){
cin>>a>>b>>c>>d;
for(int i=0;i<a;i++)
cin>>wei[i];//输入每个城市的救援人数
fill(edge[0],edge[0]+501*501,inf);//将数组的初值置为inf
fill(dis,dis+501,inf);//同上,按照单元进行赋值(memset为对字节进行填充字符,一般来填充char型数组,如果填充int型的数组,则只能填充0和-1)
//memset(a,0,sizeof a)|||fill(v.begin(),v.end(),0)
int e,f,g;
for(int i=0;i<b;i++){
cin>>e>>f>>g;
edge[e][f]=edge[f][e]=g;//边集与边的长度(有向图所以需要e->f和f->e)
}
dis[c]=0;//当前的点的值置为0
w[c]=wei[c];//更新救援队总数
num[c]=1;//出发点到当前结点的最短路径的条数为1
for(int i=0;i<a;i++){
int u=-1,minn=inf;//u用作访问标记
for(int j=0;j<a;j++){
if(visit[j]==false&&dis[j]<minn){//点集没有被访问过而且路径的长度小于最小值
u=j;//找到最小边的点集
minn=dis[j];//更新最小值
}
}
if(u==-1)
break;//如果都被访问过了,则跳出
visit[u]=true;//置当前的访问标记为true
for(int v=0;v<a;v++){
if(visit[v]==false&&edge[u][v]!=inf){//如果没有被访问过而且边集有效
if(dis[u]+edge[u][v]<dis[v]){//如果加上当前边的权值小于总的权值,则更新它
dis[v]=dis[u]+edge[u][v];
num[v]=num[u];//更新num
w[v]=w[u]+wei[v];//更新救援队的人数
}else if(dis[u]+edge[u][v]==dis[v]){//如果最小的路径相等
num[v]=num[v]+num[u];//num相加
if(w[u]+wei[v]>w[v])//如果救援队的人数有更多的选择,则更新
w[v]=w[u]+wei[v];
}
}
}
}
cout<<num[d]<<" "<<w[d];//输出
return 0;
}
四.Dijkstra算法
1.最短路径
- 单源最短路径(源点到其他各顶点的最短路径的长度):Dijkstra,Bellman-ford,SPFA
- 全局最短路径(图中任意两个点的最短路径):Floyed
- SPFA算法可以求带负权边的最短路径
2.Dijkstra算法板子
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用来标注当前结点的前一个结点
}
}
}
}
//邻接表
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);
}
- 三种考法
//新增边权（第二标尺），要求在最短路径有多条时要求路径上的花费之和最小
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];
num[u] = num[v];
}else if(dis[u] + e[u][v] == dis[v]) {
num[v] = num[v] + num[u];
}
}
}
