首页 > 其他分享 >P3106 [USACO14OPEN] Dueling GPSs S —— 最短路 图论

P3106 [USACO14OPEN] Dueling GPSs S —— 最短路 图论

时间:2024-11-29 11:21:49浏览次数:6  
标签:GPSs P3106 time USACO14OPEN Farmer FJ John road GPS

[USACO14OPEN] Dueling GPSs S

题面翻译

Farmer John 最近在网上购买了一台新车,然而当他给这台新车挑选额外设备时他不小心快速地点击了“提交” 按钮两次,因此这台新车配备了两台 GPS 导航系统!更糟糕的是,两台系统对 Farmer John 的出行路线经常做出相互冲突的决定。

Farmer John 居住的区域包含 \(N\) 个结点(\(2 \le N \le 10000\))和 \(M\) 条有向道路(\(1 \le M \le 50000\))。第 \(i\) 条道路从 \(A_i\) 连向 \(B_i\)(\(1 \le A_i, B_i \le N\))。多条道路可能连接同样一对结点,而一条双向道路是由两条单独的反向的道路来表示的。 Farmer John 的家在结点 \(1\),他的农场在结点 \(N\)。数据保证从家出发经过一系列有向道路可以到达农场。

两台 GPS 系统的内置地图都如上所描述。然而,它们对通过每条道路所需时间的预计是不同的。第一台和第二台 GPS 系统预测通过道路 \(i\) 需要花费的时间分别为 \(P_i\) 和 \(Q_i\) 个单位时间(通过每条道路所需时间是一个在 \([1, 10^5]\) 内的整数)。

Farmer John 想要从他的家去往农场。然而,当 Farmer John 通过了一条道路(假设是从 \(X\) 到 \(Y\)),而一台 GPS 系统认为这条道路不是从 \(X\) 前往农场的最短路径中的一部分时,这台 GPS 系统就会大声抱怨(如果两台 GPS 系统都认为该条道路都不是最短路径的一部分时,两台系统会同时抱怨)。

请帮助 Farmer John 求出,如果 Farmer John 合理地选择出行路线,两台 GPS 系统抱怨次数总和的最小值。如果 Farmer John 通过了一条路时两台 GPS 系统同时抱怨,那么抱怨次数增加 \(2\)。

题目描述

Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the "Submit" button twice when selecting extra features for the car, and as a result the car ended up equipped with two GPS navigation systems! Even worse, the two systems often make conflicting decisions about the route that FJ should take.

The map of the region in which FJ lives consists of N intersections (2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000). Road i connects intersections A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N). Multiple roads could connect the same pair of intersections, and a bi-directional road (one permitting two-way travel) is represented by two separate directional roads in opposite orientations. FJ's house is located at intersection 1, and his farm is located at intersection N. It is possible to reach the farm from his house by traveling along a series of directional roads.

Both GPS units are using the same underlying map as described above; however, they have different notions for the travel time along each road. Road i takes P_i units of time to traverse according to the first GPS unit, and Q_i units of time to traverse according to the second unit (each travel time is an integer in the range 1..100,000).

FJ wants to travel from his house to the farm. However, each GPS unit complains loudly any time FJ follows a road (say, from intersection X to intersection Y) that the GPS unit believes not to be part of a shortest route from X to the farm (it is even possible that both GPS units can complain, if FJ takes a road that neither unit likes).

Please help FJ determine the minimum possible number of total complaints he can receive if he chooses his route appropriately. If both GPS units complain when FJ follows a road, this counts as +2 towards the total.

输入格式

* Line 1: The integers N and M.

Line i describes road i with four integers: A_i B_i P_i Q_i.

输出格式

* Line 1: The minimum total number of complaints FJ can receive if he routes himself from his house to the farm optimally.

样例 #1

样例输入 #1

5 7 
3 4 7 1 
1 3 2 20 
1 4 17 18 
4 5 25 3 
1 2 10 1 
3 5 4 14 
2 4 6 5

样例输出 #1

1

提示

There are 5 intersections and 7 directional roads. The first road connects from intersection 3 to intersection 4; the first GPS thinks this road takes 7 units of time to traverse, and the second GPS thinks it takes 1 unit of time, etc.

If FJ follows the path 1 -> 2 -> 4 -> 5, then the first GPS complains on the 1 -> 2 road (it would prefer the 1 -> 3 road instead). However, for the rest of the route 2 -> 4 -> 5, both GPSs are happy, since this is a shortest route from 2 to 5 according to each GPS.

分析

建反图,用spfa求出终点到其他点的最短路。

然后枚举每条边,对于 $ dis[u] + e[i].z == dis[v] $ 的边打标记,为 $ GPS_1 / GPS_2 $ 的最短路径。

最后在原图上跑spfa。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100,M=5e5+100,INF=2e9;
struct edge{int x,y,n,sp[2];}e[M<<1],t[M<<1];
int n,m;
int head[N],cnt;
int dh[N],tot;
int dis[5][N],q[M],len1,len2;
int pre[2][M];
bool vis[N];
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,sp1,sp2;i<=m;++i)
    {
        scanf("%d%d%d%d",&x,&y,&sp1,&sp2);
        ++cnt;
        e[cnt].n=head[x];
        e[cnt].y=y;
        e[cnt].sp[0]=sp1;
        e[cnt].sp[1]=sp2;
        head[x]=cnt;

        ++tot;
        t[tot].n=dh[y];
        t[tot].y=x;
        t[tot].sp[0]=sp1;
        t[tot].sp[1]=sp2;
        dh[y]=tot;
    }
}

void sp(int op,edge e[],int st,int head[])
{
    int he=1,ta=0;
    for(int i=1;i<=n;++i)dis[op][i]=INF;
    dis[op][st]=0;
    q[++ta]=st;
    while(he<=ta)
    {
        int u=q[he++];
        vis[u]=0;
        for(int i=head[u];i;i=e[i].n)
        {
            int v=e[i].y;
            if(dis[op][v]>dis[op][u]+e[i].sp[op])
            {
                dis[op][v]=dis[op][u]+e[i].sp[op];
                if(!vis[v])
                {
                    vis[v]=1;
                    q[++ta]=v;
                }
            }
        }
    }

}
void go(int op)
{
    int he=1,ta=0;
    for(int i=1;i<=n;++i)dis[op][i]=INF;
    dis[op][1]=0;
    q[++ta]=1;
    while(he<=ta)
    {
        int u=q[he++];
        vis[u]=0;
        for(int i=head[u];i;i=e[i].n)
        {
            int v=e[i].y;
            int val=2-pre[0][i]-pre[1][i];
            if(val+dis[op][u]<dis[op][v])
            {
                dis[op][v]=val+dis[op][u];
                if(!vis[v])
                {
                    vis[v]=1;
                    q[++ta]=v;
                }
            }
        }
    }
}
void loading()
{
    for(int i=1;i<=n;++i)
    {
        int num1=INF,num2=INF;
        for(int j=head[i];j;j=e[j].n)
        {
            int v=e[j].y;
            num1=min(num1,dis[0][v]+e[j].sp[0]);
            num2=min(num2,dis[1][v]+e[j].sp[1]);
        }
        for(int j=head[i];j;j=e[j].n)
        {
            int v=e[j].y;
            if(num1==dis[0][v]+e[j].sp[0])pre[0][j]=1;
            if(num2==dis[1][v]+e[j].sp[1])pre[1][j]=1;
        }
    }
}
void work()
{
    sp(0,t,n,dh);
    sp(1,t,n,dh);
    loading();
    go(2);
    cout<<dis[2][n];
}

int main()
{
    init();
    work();
    return 0;
}

标签:GPSs,P3106,time,USACO14OPEN,Farmer,FJ,John,road,GPS
From: https://www.cnblogs.com/Glowingfire/p/18576200

相关文章

  • LG3107 [USACO14OPEN] Odometer S 题解 (数位DP+容斥)
    题意定义一个数是神奇的当且仅当这个数中有一个数位出现了一半及以上,比如112,2233。求\([l,r]\)中有多少个好的数字,\(100\lel,r\le10^{18}\)。题解考虑数位DP,先把答案转为\(Ans(r)-Ans(l-1)\),我们钦定一个数\(k\)让他必须出现多于一半,然后我们想求\([1,x]\)中有多少......
  • GPSSWorld初级程序编写套路
    1.仿真用时间控制:generate16,9...terminategenerate 240terminate 1start 12.仿真预热: start 5,np reset start 203.理发师选择有偏好:transfer both,adda,addbadda seize s_a …addb seize s_b …4.理发师选择没有偏好:(1)方法1:概率......
  • Gpssworld仿真(二):并排排队系统模拟
    4.3某一个加油站能够配给三个级别的燃油:①家庭取暖用的燃油;②轻工业用的燃油;③运输用的燃油。每一级别的燃油都有一个对应的油泵。订单中燃油的数量在3000加仑和5000加仑中变化,每次增加10加仑,是均匀分布。这个站点最多能容纳12辆车。来加油站装油的汽车到达的平均时间间隔是18分......
  • GPSSworld仿真(一):程序题——单窗口排队系统
    3.3一个仓库共存放了2000吨货物,货物以三种规模出库,少量(10吨),中等(20吨),大量(50吨),分别以10±5分,15分,30±10分的速率出库。如果没有货位达到的情况下,一个仓库能维持供货多少时......