文章目錄
題目分析
來源：acwing
分析：
首先這是一道dijkstra算法求最短路的題目，不過此題較為復雜。首先需要將字符串城市名映射成數字，這里使用hash table 名為city_number. 此外，還需要存路徑pre[N]數組，當然本題多的是求最短路的條數，使用cnt[N]數組； 多的是求幸福度最大，使用sum[N]數組；多的是統計結點數量，使用num[N]數組。
ac代碼
#include<bits/stdc++.h>
using namespace std
;
const int N
= 210;unordered_map
<string
,int> city_number
;
string city
[N
]; bool st
[N
];
int w
[N
];
int c
[N
][N
];
int dist
[N
];int sum
[N
];
int num
[N
];
int cnt
[N
];
int pre
[N
];int n
, m
;
string S
; void dijkstra(){memset(dist
, 0x3f, sizeof dist
);dist
[0] = 0 ,cnt
[0] =1; num
[0]=0,sum
[0]=0;for(int i
= 0; i
< n
; i
++){int t
= -1;for(int j
=0; j
< n
; j
++)if(!st
[j
] &&(t
== -1 || dist
[j
]<dist
[t
]))t
= j
;st
[t
] =true;for( int j
= 1; j
< n
; j
++){if(dist
[j
] > dist
[t
] + c
[t
][j
]){dist
[j
] = dist
[t
] + c
[t
][j
];sum
[j
] = sum
[t
] +w
[j
];num
[j
] =num
[t
] +1;cnt
[j
] =cnt
[t
];pre
[j
] =t
;}else if(dist
[j
] == dist
[t
]+ c
[t
][j
]){cnt
[j
]+=cnt
[t
];if(sum
[j
]< sum
[t
] + w
[j
]){sum
[j
] = sum
[t
] +w
[j
];num
[j
] = num
[t
] +1;pre
[j
] =t
;}else if(sum
[j
] == sum
[t
] + w
[j
]){if(num
[j
] >num
[t
] + 1){num
[j
] =num
[t
] +1;pre
[j
] =t
;}}}}}}int main(){memset(c
,0x3f, sizeof c
);cin
>> n
>> m
>> city
[0];city_number
[city
[0]] = 0; for(int i
= 1; i
<n
;i
++){int content
;cin
>> city
[i
] >>content
;city_number
[city
[i
]] =i
; w
[i
] =content
;}while(m
--){string c1
,c2
;int a
;cin
>> c1
>> c2
>> a
;int n1
= city_number
[c1
],n2
= city_number
[c2
];c
[n1
][n2
] = c
[n2
][n1
] =min(c
[n1
][n2
], a
); }dijkstra();int T
= city_number
["ROM"]; cout
<< cnt
[T
] << ' '<< dist
[T
] <<" " << sum
[T
] <<" "<<sum
[T
]/num
[T
]<<endl
;vector
<int> path
;for(int i
=T
; i
!=0; i
=pre
[i
]) path
.push_back(i
); cout
<<city
[0];for(int i
=path
.size()-1; i
>=0; i
--) cout
<<"->"<<city
[path
[i
]];}
題目鏈接
PAT甲級1087 All Roads Lead to Rome (30分)
https://www.acwing.com/problem/content/1579/
總結
以上是生活随笔為你收集整理的PAT甲级1087 All Roads Lead to Rome (30分)：[C++题解]dijkstra求单源最短路综合、最短路条数、保存路径的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
