#include<stdio.h>
#include<string.h>
#define MAXVEX 100 // 定義的最大定點數
#define INFINITY 65535 //定義一個極大數
int final[MAXVEX];//為1即代表當前坐標的最短路徑已經找到
int map[MAXVEX][MAXVEX];//代表權值
int m,n;//分別表示幾個城市
int num[MAXVEX];//最短路徑條數
int team[MAXVEX];//可集結的最多救援隊數量
int dis[MAXVEX];//存放所有結點的權值
int city[MAXVEX];//代表救援隊的數目
int c1,c2;//初始結點和目標結點

int main()
{
void Dijkstra();
scanf("%d %d %d %d",&m,&n,&c1,&c2); //m代表城市數量，n代表路數量
memset(final,0,n);//將所有節點設置為未被訪問
for(int i=0;i<m;++i)
{
scanf("%d",&city[i]);//給城市數量的救援人數賦值
}
for(int i=0;i<m;++i)
{
for(int j=0;j<m;++j)
{
//給每條路賦權值,注意是所有路都賦極大值INFINITY
map[i][j] = INFINITY;
}

}
for(int i=0;i<n;++i)//給n條路設定值
{

int start,end,length;// 起點，終點，起點到終點的權值
scanf("%d %d %d",&start,&end,&length);
map[start][end] = length;
map[end][start] = length;//雙向賦值
}
Dijkstra();
printf("%d %d",num[c2],team[c2]);
return 0;

}

void Dijkstra(){
int ct;//設置一個中間節點
for(int i=0;i<m;++i){
//把到沒個結點的權值都存放入數組中
dis[i] = map[c1][i];//從c1開始
}
memset(num,0,m);//給m個結點的最短路徑條數都初始化為0
memset(team,0,m);//給m個結點的救援人員總數量都初始化為0
num[c1] = 1;//表示c1這個節點的路徑為1
dis[c1] = 0;//到c1的權值為0;
team[c1] = city[c1];
ct = -1;//將中間結點賦值為-1做標記
while(c1!=c2){
int min = INFINITY;//設置一個最小距離值
for(int i=0;i<m;++i)
{
if(!final[i]&&dis[i]<min){
min = dis[i];
ct = i;//此ct相當于【大話數據結構】dijastra算法中的k
}
}
final[ct] = 1;//表示當前結點的最短路徑已經求得
for(int i=0;i<m;++i) {//這個循環尤其重要，用來修正路徑權值 *****************************
if(!final[i]){
if(dis[i]>min+map[ct][i]){
dis[i] = min + map[ct][i];
team[i] = city[i]+team[ct];
num[i] = num[ct];

} else if(dis[i] == min + map[ct][i])
{
num[i] = num[i] + num[ct];
if(team[i]<team[ct]+city[i])
team[i] = team[ct] + city[i];
}
}
}
}
}

轉載于:https://www.cnblogs.com/purpleone/p/10822421.html

總結

以上是生活随笔為你收集整理的1003 Dijkstra算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。