dijkstra算法简介

算法特点

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法思路(单源点)

Dijkstra算法采用的是一种贪心的策略，声明一个数组d来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：d，初始时，原点 s 的路径权重被赋为 inf(比较大的一个数)；初始化，遍历源点能到的点u，更新d[u]（如果能到肯定<inf）；初始化后，再次遍历能到达的点u，通过u中间点遍历其余点v，若d[u]+g[u][v]<d[v],则更新d[v]，遍历结束，数组d即为最终源点到达其余点的最短距离。

dijkstra算法例题pat 1003 Emergency (25 分)

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, C​1​​ and C​2- 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​​ , c​2 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 C​2​​ .

Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between C​1 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 spaceallowed 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

代码（注释）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//无向图
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxx=510;  //最大顶点数
const int inf =1e9;   //无连通的边
int n,m,st,ed,g[maxx][maxx],weight[maxx]; //weight为点权
int d[maxx],w[maxx],num[maxx]; //d记录最短距离，w记录最短路径的最大点权之和，num记录最短路径数
bool vis[maxx]={false}; //记录该点是否访问

void dijkstra(int s)
{
    fill(d,d+maxx,inf); //初始化d
    memset(num,0,sizeof(num)); //初始化
    memset(w,0,sizeof(w)); //初始化
    d[s]=0; //起始点记录为0
    w[s]=weight[s]; //起始点权重
    num[s]=1; 
    for(int i=0;i<n;i++) //遍历
    {
        int u=-1,minn=inf; //u记录最短路径下标,minn存放最小d[u]
        for(int j=0;j<n;j++) //找到未访问的顶点中d[u]最小的
        {
            if(vis[j]==false&&d[j]<minn) //
            {
                u=j;
                minn=d[j];
            }
        }
        if(u==-1)return ; //找不到直接返回结束
        vis[u]=true; //找到后标记
        for(int v=0;v<n;v++) //遍历
        {
            if(vis[v]==false&&g[u][v]!=inf)//找到未被标记且能到达的V点
            {
                if(g[u][v]+d[u]<d[v])//以U为中介点更短则更新d,w,num
                {
                    d[v]=g[u][v]+d[u];
                    w[v]=w[u]+weight[v];
                    num[v]=num[u];
                    
                }
                else if(g[u][v]+d[u]==d[v])//如果相等，则判断权值的大小
                {
                    if(w[u]+weight[v]>w[v])
                        w[v]=w[u]+weight[v];
                    num[v]+=num[u]; //更新路径数
                }

            }
        }
    }
}

int main()
{
    cin>>n>>m>>st>>ed;
    for(int i=0;i<n;i++)
        cin>>weight[i];
    int u,v;
    fill(g[0],g[0]+maxx*maxx,inf); //初始化图
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        cin>>g[u][v];
        g[v][u]=g[u][v];  //无向图
    }
    dijkstra(st);
    cout<<num[ed]<<' '<<w[ed]<<endl;
	return 0;
}