首页 > 代码库 > usaco 过路费 Cow Toll Paths, 2009 Dec

usaco 过路费 Cow Toll Paths, 2009 Dec

2024-08-18 06:42:18   219人阅读

Description

翰家有 N 片草地，编号为 1 到 N ，彼此之间由 M 条双向道路连接，第 i 条道路连接了 Ai 和Bi，两片草地之间可能有多条道路，但没有道路会连接同一片草地，现有的道路可以保证任意两片草 地都是连通的。

有一天，约翰宣布奶牛走路要收过路费，只要奶牛走过第 i 条道路，就要收费 Li 元。此外，约 翰还要求每头奶牛购买牌照，他为每片草地设置了牌照标准，如果奶牛购买的牌照价格低于某片草地 的标准，她将被禁止进入那片草地。第 i 片草地的牌照标准为 Ci。

新政策一出，奶牛们敢怒不敢言，有 Q 头奶牛向你咨询最省钱的走路办法，第 i 头奶牛要从草地Si 走到 Ti。请你帮她们算算，选择什么样的路线才能最省钱？

Input Format

第一行：三个整数 N ，M 和 Q，1 ≤ N ≤ 250; 1 ≤ M ≤ 10000; 1 ≤ Q ≤ 10000

? 第二行到第 N + 1 行：第 i + 1 行有一个整数 Ci，1 ≤ Ci ≤ 10^6

? 第 N + 2 行到第 N + M + 1 行：第 i + 1 行有三个整数 Ai，Bi 和 Li，1 ≤ Ai ; B i ≤ N ,1 ≤ Li ≤ 10^6

? 第 N + M +2 行到第 N + M + Q +1 行：第 i + N + M +1 行有两个整数 Si 和 Ti，1 ≤ Si,Ti ≤ N

Output Format

第一行到第 Q 行：第 i 行有一个整数，表示从 Si 到 Ti 的最低费用是多少

Sample Input

样例输入
5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3

Sample Output

样例输出
8
9
解释
最 好 办 法 分 别 是 1 → 3 → 5 → 4 和
2 → 5 → 3


一题不错的floyed图论题；要吃透了floyed才能打出正解；
首先最暴力打法就是枚举牌照；那么时间复杂度就会达到n^4；40%；
数据中 n<=250;那么我们很显然要考虑优化；n^3?;
可floyed中的起始点和终止点和过渡点是没法省略的；
那方向就明确了；要把枚举路牌那维降到o(1);
我们仔细想想 这些路径有以下性质
不妨设s为起点；t为终点；
1：路牌费用越大 那么s->t的路程是非上升的序列；
2：路径上最大路牌的费用+路程=总费用；
那么我们将每个点的点权进行排序，然后从小到大枚举过渡点进行floyed；100%；
排序的合理性在于 由于路径满足性质 1；所以在floyed过程中最短路会持续更新；
s->t的起终点不变；过渡点点权持续增加那么 路径的最大点权也会持续更新；
那就可以考虑到所有的情况 是合理的；
核心程序
bool cmp(const st x,const st y)
{
    if(x.w<y.w)return true;
    return false;
}

std::sort(mu+1,mu+1+n,cmp);
    for(i=1;i<=n;++i)
    {
        g[i][i]=w[i];
        f[i][i]=0;
    }
    for(int z=1;z<=n;++z)
    {
        k=mu[z].id;
        for(i=1;i<=n;++i)    
        for(j=1;j<=n;++j)
        {
            f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
            g[j][i]=g[i][j]=min(g[i][j],max(w[k],max(w[i],w[j]))+f[i][j]);
        }
    }

 

usaco 过路费 Cow Toll Paths, 2009 Dec


联系
我们