【Horn Coding Studio】CPP编程专栏（狄克斯特拉-算法）

题目

题目描述

输入

第一行：三个用空格隔开的整数N,M和B。

第二到M+1行：第i+1行用R_i，S_i和L_i三个用空格隔开的整数描述双向边i。

第M+2到M+B+1行：第M+i+1行包含两个用空格隔开的整数P_i和Q_i。

输出

样例输入 

6 7 3 
1 2 3 
5 4 3 
3 1 1 
6 1 9 
3 4 2 
1 4 4 
3 2 2 
2 4 
5 1 
3 6

样例输出 

6 
6 
10

知识点普及

Dijkstra算法：详情请见算法介绍：Dijkstra 算法 - 冯子坤 - 博客园 (cnblogs.com)

一点即通

从今天起我们要使用一种新的算法，用来求最短路径问题，非常银杏，具体思路就是：让一只奶牛跑到FJ那边，然后再跑回p_i那里。细心的朋友都发现了，这样太慢！！！而且常量开这么大跑两遍确实非常勉强。

但是这数据有一点点水，水的亲妈都不认得那种。

进一步，我们发现，在第i头奶牛的行动中，肯定会经过1号点

所以，只要跑一边dijkstra就好了，把起点设为1

每当进行一次询问，就输出d[u]+d[v] ，复杂度不高，连cincout都能优秀的跑完。

代码

本次代码

ZZOJ 100%AC,25924KB空间复杂度，9MS优秀时间复杂度。

Luogu OJ 50%TLE，13789KB时间复杂度，1200MS超时

 1 #include<bits/stdc++.h>
 2 using namespace std ;
 3 const int maxn = 1000001 ;
 4 int n,m,t,k,s,e;
 5 int dis[maxn], vis[maxn], head[maxn] ;
 6 struct dy {
 7     int x, y, z,next;
 8 } a[maxn];
 9 void add(int x, int y, int z) {
10     a[t].x = x ;
11     a[t].y = y ;
12     a[t].z = z ;
13     a[t].next = head[x] ;
14     head[x] = t ++ ;
15 }
16 void dj(int s) {
17     queue<int>q ;
18     for(int i = 1 ; i <= n ; i ++) dis[i] = 1e9 ;
19     memset(vis, false, sizeof(vis)) ;
20     q.push(s) ;
21     dis[s] = 0 ;
22     while(!q.empty()) {
23         int u = q.front() ;
24         q.pop() ;
25         vis[u] = 0 ;
26         for(int i = head[u] ; i != -1 ; i = a[i].next ) {
27             int v = a[i].y ;
28             if(dis[v] > dis[u] + a[i].z) {
29                 dis[v] = dis[u] + a[i].z ;
30                 if(!vis[v]) {
31                     vis[v] = true ;
32                     q.push(v) ;
33                 }
34             }
35         }
36     }
37 }
38 int p ;
39 int main() {
40     cin >> n >> m >> p ;
41     memset(head, -1, sizeof(head)) ;
42     while(m --) {
43         int x, y, z ;
44         cin >> x >> y >> z ;
45         add(x, y, z ) ;
46         add(y, x, z) ;
47     }
48     while( p --) {
49         cin >> s >> e ;
50         dj(s) ;
51         int w = dis[1] ;
52         dj(1) ;
53         cout << w + dis[e] <<endl;
54     }
55 }
56 /**************************************************************
57     User: FZK
58     Language: C++
59     Result: 正确
60     Time:9 ms
61     Memory:29524 kb
62 ****************************************************************/

笑一笑