题解 P3115 【[USACO15JAN]牛路线Cow Routing】

发表于 | 评论数： | 阅读次数：
本文字数： 4.5k | 阅读时长 ≈ 4 分钟

-1.前置知识

最短路，图论

0.大体思路

对每条航线进行建边处理，同时记录两个城市之间的城市数(这里题目中的经过多少城市指从$u$到$v$不包括首/尾的城市数)，然后跑$Dijkstra$即可

1.建边

本题由于边数较多，采用邻接矩阵存图较为合适。

定义$cost[i][j]$表示从$i$到$j$的最少费用，$to[i][j]$表示在费用最少的情况下从$i$到$j$所经过的最少城市数

假设一条航线的费用是$money$,有$len$个城市，对应的编号分别为$x_{1},x_{2},···,x_{len}$

首先要明确一个常识性问题：在一条航线上，一个城市不能飞到它之前的城市

所以我们可以得到一个显然的建边方法，对于一条航线的$x_{i}$，向$x_{j}(i<j<=len)$建一条长度为$money$的边。需要注意的是，如果之前$cost[i][j]$已赋值，则

  • 如果$money<cost[i][j]$，需要更新$cost[i][j],to[i][j]$

  • 如果$money=cost[i][j]$，则如果$i$到$j$之间的城市数$<to[i][j]$，更新$to[i][j]$

这样就可以满足在花费最少的情况下经过的城市数最少

2.Dijkstra

定义$c[i]$为起点到$i$的最少花费，$ans[i]$为起点到$i$之间经过的城市数

假设当前从城市$k$开始拓展。

如果$k$与某个城市$i$有连边$cost[k][i]$，我们可以类比之前建边的方法进行更新。

  • 如果$c[k]+cost[k][i]<c[i]$，更新$c[i],ans[i]$

  • 如果$c[k]+cost[k][i]=c[i]$，如果$ans[k]+to[k][i]<ans[i]$，更新$ans[i]$

其中$ans[i]$的更新是指$ans[i]=ans[k]+to[k][i]$

根据定义，$ans[i]$表示起点到$i$的城市数，$ans[k]$表示起点到$k$的城市数，$to[k][i]$表示$k$到$i$之间的城市数，所以很明显有$ans[i]=ans[k]+to[k][i]$

3.Code

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
#include <bits/stdc++.h>
using namespace std;

int read()//快读
{
        int sum = 0, f = 1;
        char c = getchar();
        while(c < '0' or c > '9')
        {
                if(c == '-') f = -1;
                c = getchar();
        }
        while(c >= '0' and c <= '9')
        {
                sum = (sum << 1) + (sum << 3) + c - '0';
                c = getchar();
        }
        return sum * f;
}

int a, b, n, len, maxn;
int cost[1010][1010], x[10010], to[1010][1010], money, ans[1010];
unsigned long long c[1010];//别忘了开long long
priority_queue<pair <long long, int> > q;
bool vis[1010];

void Dijkstra()//堆优化Dij
{
        for(int i = 1; i <= maxn; i++) c[i] = LONG_LONG_MAX;
        c[a] = 0;
        q.push(make_pair(0, a));
        while(!q.empty())
        {
                int k = q.top().second;
                q.pop();
                if(vis[k]) continue;
                vis[k] = 1;
                for(int i = 1; i <= maxn; i++)
                        if(cost[k][i] != 1e9 + 10)//有连边
                        {
                                if(c[i] > c[k] + cost[k][i])
                                {
                                        c[i] = c[k] + cost[k][i];
                                        ans[i] = ans[k] + to[k][i];
                                        q.push(make_pair(-c[i], i));
                                }
                                else
                                {
                                        if(c[i] == c[k] + cost[k][i])
                                        {
                                                if(ans[i] > ans[k] + to[k][i]) ans[i] = ans[k] + to[k][i];
                                        }
                                }
                        }
        }
}

int main()
{
        for(int i = 1; i <= 1010; i++)
                for(int j = 1; j <= 1010; j++)
                        cost[i][j] = 1e9 + 10;//赋初值
        memset(to, 127, sizeof(to));//赋初值
        a = read(), b = read(), n = read();
        //建边
        for(int i = 1; i <= n; i++)
        {
                money = read(), len = read();
                for(int j = 1; j <= len; j++)
                        x[j] = read(), maxn = max(maxn, x[j]);
                for(int j = 1; j <= len; j++)
                {
                        for(int k = j + 1; k <= len; k++)
                        {
                                if(cost[x[j]][x[k]] > money)
                                        cost[x[j]][x[k]] = money, to[x[j]][x[k]] = k - j;//k-j就是j到k之间的城市数（不包含首尾）
                                else
                                if(cost[x[j]][x[k]] == money)
                                {
                                        if(k - j < to[x[j]][x[k]])
                                        {
                                                to[x[j]][x[k]] = k - j;
                                        }
                                }
                        }
                }
        }

        Dijkstra();

        if(c[b] != LONG_LONG_MAX)//判断是否能到达
        {
                printf("%lld %d", c[b], ans[b]);
        }
        else
        {
                printf("-1 -1");
        }
        return 0;
}