单源最短路径（标准版）

题目描述：

与弱化版的单圈最短路径题（即P3371）的题目比较，主要有两个不同点（其他的基本不变）：

　　1.此题中说明了所给的测试数据能保证起始点访问到所有的点

　　2.很明显，这个题的时间限制更加严格

题解：因此要解决此题，我们可以再P3371的基础上（代码链接）进行修改+优化，即可达到此题的要求。

　　针对于不同点1，P3371的基础上将if(color[j]==BLACK||a[u][j]==0) continue;改为了if(color[j]==BLACK) continue; 因为题目已经有保证了，没必要判断不同点之间是否有边连接，反而这个操作会限制本来有边连接（但权值没来得及更新仍然为0）的后续更新，因此此处去掉。

　　针对于不同点2，采用3个优化操作：（储存结构依然用前向星）

　　　　①在遍历变量的时候采取register int，加快速度，减少TLE的出现概率。register int的具体解释见：这里

　　　　②在各节点出队的时候加上if(color[u]==BLACK) continue;来减少点重复出队

　　　　③最关键的点：采用堆排序或者是优先队列，将O（n^2)的复杂度降到O(nlogn)。即在每次寻找距离源点的最小节点部分，采用优先队列（最小堆）来代替，优化此处操作。

 1 #include<bits/stdc++.h>
 2 #define re register 
 3 using namespace std;
 4 int MAX=100005;
 5 int INFTY=2147483647;
 6 int WHITE=0;
 7 int BLACK=1;
 8 int GRAY=2;
 9 int n,m,s;
10 typedef pair<int,int> P;
11 struct edge{
12     int next;        //下一条相邻边的编号 
13     int to;            //当前边的终止点的号码 
14     int w;        //权值 
15 }e[500010];
16 int head[100005];     //head[i]表示与i所有相连接的边中第一条边的编号 
17 int cnt=0;            //代表边的编号从0开始 
18 
19 //邻接矩阵+优先队列 
20 //使用了优先队列  便省去了找当前最小权值点的步骤 因为最小值始终在队头 
21 void dijkstra(){
22     priority_queue<P,vector<P>,greater<P> > PQ;        //priority默认从大到小输出        first为边权值 second为点的编号 
23                                                     //加上vector<P>,greater<P>改为从小到大输出 
24                                                     //优先队列PQ判断大小的依据是PQ的first成员 
25     int color[MAX];
26     int d[MAX];
27     for(re int i=1;i<=n;i++){
28         d[i]=INFTY;
29         color[i]=WHITE;
30     }
31     d[s]=0;
32     
33     PQ.push(make_pair(0,s));
34     color[s]=GRAY;
35     
36     while(!PQ.empty()){
37         P f=PQ.top();
38         PQ.pop();
39         int u=f.second;            //u即是当前权值最小的结点编号 
40         
41         if(color[u]==BLACK) continue;        //之间访问过（即有入队出队经历）便不再访问   此处是一个优化剪枝 
42         color[u]=BLACK;
43         
44         int temp=head[u];            //temp为与顶点u连接的第一条边的编号
45         for(re int k=temp;~k;k=e[k].next){
46             if(color[e[k].to]==BLACK) continue;            //修改地方：由于题目确保各点都能访问到，所以删除了判断各边是否有连接的部分 
47             
48             if(d[e[k].to]>d[u]+e[k].w) {
49                 d[e[k].to]=d[u]+e[k].w;
50                 PQ.push(make_pair(d[e[k].to],e[k].to));
51                 
52                 color[e[k].to]=GRAY; 
53             }
54         }
55     }
56     for(re int i=1;i<=n;i++){
57         cout<<d[i]<<" ";
58     }
59 }
60 void add(int u,int v,int w){
61     e[cnt].to=v;
62     e[cnt].w=w;
63     e[cnt].next=head[u];        //表示当下边的下一条边是与u连接的第1条边  有前插的思想 
64     head[u]=cnt;                //更新当前边为与u连接的第一条边 
65     cnt++; 
66 } 
67 int main(){
68     int u,v,w;
69     memset(head,-1,sizeof(head));
70     cin>>n>>m>>s;        //注意 题目所给的编号范围是1-n 所以使用模板时需要注意修改范围 
71     for(re int i=1;i<=m;i++){
72         cin>>u>>v>>w;
73         add(u,v,w);
74     }
75     
76     dijkstra();
77     return 0;
78 }