题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1459
题意：中文题诶～
思路：带权值的最短路，这道题数据也没啥特殊，spaf，floyd, dijkstra 都可以过，我这里就写个dijkstra好了．．．
dijkstra算法和最小生成树的prime有点像，prime算法是将所有点分成两个点集s, w，初始时s中只有一个点，然后依次将w中距离s集合最近的点加入s集合中，直至w为空集．．
这两个算法的区别是dijkstra还要依次以点集s为中间点来更新点集w中的点到出发点的最小距离，最终自然能得到出发点到终止点的最小距离啦．．
dijkstra模板中更新出发点到w点集的距离时不需要考虑距离相同的情况，而本题则需要更新为权值更大的点即可．．．
1 #include <bits/stdc++.h>
2 #define INF 1000000000
3 #define MAXN 1000
4 using namespace std;
5
6 int mp[MAXN][MAXN], low[MAXN], tag[MAXN], n, m, rank[MAXN], vis[MAXN];
7 // low[j]记录出发点到点j的最短距离，tag[j]标记点j是否被选中过, vis[j]记录出发点到点j的最大权值
8
9 void dijkstra(int s, int e){
10 for(int i=0; i<n; i++){ //初始化
11 low[i]=mp[s][i];
12 }
13 vis[s]=rank[s];
14 low[s]=0;
15 for(int i=0; i<n; i++){
16 int MIN=INF;
17 for(int j=0; j<n; j++){
18 if(low[j]<MIN&&!tag[j]){
19 MIN=low[j];
20 s=j; //s为当前选中的点
21 }
22 }
23 tag[s]=1;
24 for(int j=0; j<n; j++){ //更新各点到出发点的最小距离
25 if(low[j]>mp[s][j]+low[s]){
26 low[j]=mp[s][j]+low[s];
27 vis[j]=vis[s]+rank[j];
28 }else if(low[j]==mp[s][j]+low[s]){ //若距离相等则更新权值更大的点
29 vis[j]=max(vis[s]+rank[j], vis[j]);
30 }
31 }
32 }
33 cout << low[e] << " " << vis[e] << endl;
34 }
35
36 int main(void){
37 int s, e;
38 cin >> n >> m >> s >> e;
39 for(int i=0; i<n; i++){
40 cin >> rank[i];
41 }
42 for(int i=0; i<n; i++){
43 for(int j=0; j<n; j++){
44 mp[i][j]=mp[j][i]=INF;
45 }
46 }
47 while(m--){
48 int x, y, z;
49 cin >> x >> y >> z;
50 mp[x][y]=mp[y][x]=z;
51 }
52 dijkstra(s, e);
53 return 0;
54 }
原文：http://www.cnblogs.com/geloutingyu/p/6244474.html