一捅儒、題目
image.png
image.png
二脂倦、注意
- dijkstra
- dijkstra算法的實(shí)現(xiàn)
- 解決已選元素集合s畅厢， bool vis[n]
- 解決起點(diǎn)到各頂點(diǎn)最短路徑冯痢，int d[n]
- 解決最短路徑的條數(shù)氮昧，int num[n]
- 解決最短路徑的最大頂點(diǎn)權(quán)值之和框杜，int w[n]
- 如何輸出最短路徑（當(dāng)最短路徑唯一時(shí)）
#include <algorithm>
//使用fill，給數(shù)組賦初始值
//1. fill(首地址袖肥，終地址咪辱，初值)
//2. 一維數(shù)組int A[n]的首地址為：A
//3. 二維數(shù)組int A[n][n]的首地址為：A[0]，同樣也是第一行的首地址
int num[MAXV]; //最短路徑的條數(shù)
fill(num, num + MAXV,0);
- dijkstra的變體問題：碰到有兩條及以上可以到達(dá)最短距離的路徑椎组，存在兩個(gè)尺度：第一個(gè)尺度——距離油狂；第二個(gè)尺度——可以是邊權(quán)（花費(fèi)）、點(diǎn)權(quán)等寸癌。要求在最短路徑中专筷，也就是選擇在第一個(gè)尺度的基礎(chǔ)上，使得第二個(gè)尺度的最優(yōu)的一條路徑蒸苇。常見的第二尺度如下：
- 給每條邊增加一個(gè)邊權(quán)（花費(fèi)）磷蛹，然后要求在最短路徑的有多時(shí)要求路徑上的花費(fèi)之和最小
- 給每個(gè)點(diǎn)增加一個(gè)點(diǎn)權(quán)（例如每個(gè)城市能收集到的物資），然后在最短路徑有多條時(shí)要求路徑上的點(diǎn)權(quán)之和最大
- 直接詢問有多少條最短路徑
- 單詞：
- the number of different shortest paths between C1 and C2: C1到C2之間最短路徑的條數(shù)
- the maximum amount of rescue teams you can possibly gather：你可以獲得的最大營救隊(duì)的數(shù)量
- scattered: 分散的
- call up as many hands on the way as possible: 在這條路上召集盡可能多的人
三溪烤、思路代碼
#include <iostream>
#include <algorithm>
//使用fill味咳，給數(shù)組賦初始值
//1. fill(首地址庇勃，終地址，初值)
//2. 一維數(shù)組int A[n]的首地址為：A
//3. 二維數(shù)組int A[n][n]的首地址為：A[0]槽驶，同樣也是第一行的首地址
using namespace std;
const int MAXV = 500; //頂點(diǎn)數(shù)最大值
const int INF = 1000000; //最大值
int N;//城市數(shù)量
int M;//路徑的數(shù)量责嚷，邊的數(shù)量
int C1,C2;//所在城市和目標(biāo)城市
int G[MAXV][MAXV];//圖
int teams[MAXV];//點(diǎn)權(quán)
int d[MAXV]; //最短路徑
int w[MAXV]; //最大的權(quán)值之和, the maximum amount of rescue teams
int num[MAXV]; //最短路徑的條數(shù)，the number of different shortest paths between C1 and C2
bool vis[MAXV] = {false}; //標(biāo)記訪問數(shù)組
//單源最短路徑掂铐，dijskra算法
void Dijkstra(int s) //G為鄰接矩陣存儲的無向圖的結(jié)構(gòu)罕拂，C1為起點(diǎn),C2為終點(diǎn)，N為城市數(shù)量
{
//初始化全陨，最短路徑數(shù)組聂受，最短路徑數(shù)量數(shù)組，最大點(diǎn)權(quán)和數(shù)組
fill(d,d+MAXV,INF);
d[s] = 0; //起點(diǎn)到自身的距離為0
fill(num, num + MAXV,0);
fill(w,w + MAXV,0);
w[s] = teams[s]; //自己到自己的最短路徑點(diǎn)權(quán)和最大就是自己的點(diǎn)權(quán)值
num[s] = 1; //到自身的路徑至少有1條烤镐，且為最短
for(int i=0;i<N;i++) //循環(huán)N次蛋济，依次訪問N個(gè)節(jié)點(diǎn)
{
int u = -1;
int MIN = INF;
for(int j=0;j<N;j++)
{
if(vis[j]==false&&d[j]<MIN) //如果節(jié)點(diǎn)j未被訪問過，并且起點(diǎn)到節(jié)點(diǎn)j的新距離小于MIN炮叶，更新MIN
{
u=j;
MIN = d[j];
}
}
//找不到小于max的d[u],說明剩下的頂點(diǎn)與起點(diǎn)s不連通
if(u==-1)
return;
vis[u]=true; //標(biāo)記已經(jīng)訪問過
//判斷新加入的節(jié)點(diǎn)u對num[] w[] d[]造成的影響
for(int v=0;v<N;v++)
{
if(vis[v]==false && G[u][v]!=INF) //v點(diǎn)未被訪問碗旅，且u和v之間存邊
{
if(d[u]+G[u][v]<d[v]) //路徑更優(yōu)
{
d[v] = d[u]+G[u][v]; //更新更優(yōu)路徑
w[v] = w[u]+teams[v]; //在u點(diǎn)權(quán)值和的基礎(chǔ)上+v點(diǎn)權(quán)值
num[v] = num[u]; //有多少條到u的路徑，那么就有多少條到v的路徑镜悉，因?yàn)閡->v
}else if(d[u]+G[u][v] == d[v]){ //找到一條相長度的路徑
if(w[u] + teams[v] > w[v])
w[v] = w[u]+teams[v];
num[v] += num[u]; //新增一條路徑
}
}
}
}
}
int main()
{
cin >>N>>M>>C1>>C2; //輸入
fill(teams,teams+MAXV,0);//救援隊(duì)數(shù)量
for(int i=0;i<N;i++)
{
cin >>teams[i];
}
fill(G[0],G[0]+MAXV*MAXV,INF); //城市之間的道路的長度初始化為無窮大
for(int i=0;i<M;i++) //輸入構(gòu)造圖
{
int a,b,c;
cin>>a>>b>>c; //a->b的長度為c
G[a][b] = c; //讀入邊的權(quán)值
G[b][a] = c;
}
Dijkstra(C1); //求出源點(diǎn)C1到C2的最短路徑條數(shù)祟辟，在最短路徑的基礎(chǔ)上可以獲得的最多的救援隊(duì)數(shù)量
cout <<num[C2]<<" "<<w[C2];
return 0;
}
