洛谷P2984《[USACO10FEB]给巧克力Chocolate Giving》

一月 10, 2019 5568

此时一位单身🐂路过

题目描述

Farmer John有B头奶牛 (1<=B<=25000) ，有 N(2*B<=N<=50000) 个农场，编号 1\rightarrow N ，有 M(N-1<=M<=100000) 条双向边，第 i 条边连接农场 R_i 和 S_i(1<=R_i<=N;1<=S_i<=N) ，该边的长度是 L_i(1<=L_i<=2000) 。居住在农场 P_i 的奶牛 A(1<=P_i<=N) ，它想送一份新年礼物给居住在农场 Q_i(1<=Q_i<=N) 的奶牛 B ，但是奶牛 A 必须先到FJ(居住在编号 1 的农场)那里取礼物，然后再送给奶牛 B 。你的任务是：奶牛 A 至少需要走多远的路程？

输入输出格式

输入格式

第一行：三个用空格隔开的整数 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 。

输出格式

第一到 B 行：第 i 行包括一个整数，居住在农场 P_i 的公牛从FJ那里取得情人节巧克力后送给他居住在农场 Q_i 的梦中情牛至少需要走的距离。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
10
11
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

输出样例

1
2
3
6
6
10

解题思路

这道题就是给你一张图和多个询问，对于每个询问，求两个点到点 1 的最短路径之和。

由于双向边的最短路可逆，我们可以得出下面的结论：

对于两条边 (i,j) 和 (j,i) ，有

dis_{(i,j)} = dis_{(j,i)}

所以我们只需要预处理出点 1 到其他所有点的最短路，然后对于每个询问 P,Q 输出 dis_{(1,P)} + dis_{(1,Q)} 即可

代码实现

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 50000 + 10;
    const int MAXM = 100000 + 10;
    
    struct Node {
        int now, weight;
        
        Node() { now = weight = 0; }
        Node(int now, int weight) : now(now), weight(weight) {}
        
        bool operator < (const Node &that) const {
            return weight > that.weight;
        }
    };
    
    Node NewNode(int now, int weight) {
        Node tmp;
        tmp.now = now;
        tmp.weight = weight;
        return tmp;
    }
    
    struct Edge {
        int now, next, weight;
    } edge[MAXM * 2];
    
    int n, m, b, cnt, head[MAXN], dis[MAXN];
    
    inline void addEdge(int prev, int next, int weight) {
        edge[++cnt].now = next;
        edge[cnt].weight = weight;
        edge[cnt].next = head[prev];
        head[prev] = cnt;
    }
    
    inline void SFPA(int s) {
    	// 要注意的是
    	// 据说这题不卡 SPFA
    	// 但为保险起见
    	// 我还是选择 Dijkstra
        memset(dis, 0x7f7f7f7f, sizeof dis);
        dis[s] = 0;
        std::priority_queue<Node> q;
        q.push(NewNode(s, 0));
        while (!q.empty()) {
            Node NowNode = q.top();
            q.pop();
            int nownode = NowNode.now;
            for (int e = head[nownode]; e; e = edge[e].next) {
                int now = edge[e].now;
                if (dis[now] > dis[nownode] + edge[e].weight) {
                    dis[now] = dis[nownode] + edge[e].weight;
                    q.push(NewNode(now, dis[now]));
                }
            }
        }
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using FastIO::getint;
    n = getint();
    m = getint();
    b = getint();
    For (i, 1, m) {
        int prev = getint();
        int next = getint();
        int weight = getint();
        addEdge(prev, next, weight);
        addEdge(next, prev, weight);
    }
    SFPA(1);
    // 预处理出最短路
    For (i, 1, b) {
        int a = getint();
        int b = getint();
        int ans = dis[a] + dis[b];
        // 转化过的问题的答案，也是最终答案
        FastIO::putint(ans, '\n');
    }
    return 0;
}