【洛谷 4880】抓住czxx

题目背景

蒟蒻

题目描述

$czxczx放鸽子的地方是一个公园，公园珂以看作是由nn个点mm条边组成的无向图(保证无自环），ltylty将从公园的入口（bb号节点）进去寻找czxczx，czxczx刚开始的位置为ee，而czxczx会在a_iai个单位时间时变化位置到第xx个节点去，在此之前ltylty已经知道了czxczx的具体位置和接下来他位置的变化方案，蒟蒻ltylty现在想知道他至少需要花多少时间找到czxczx。$

UPD:

保证图联通，

输入格式

第一行四个整数

接下来

第

接下来 $TT行，每行两个整数a_iai和xx，表示czxczx将在第a_iai个单位时间时移动到第xx个点上去。$

输出格式

一个整数表示最短所需时间。

输入输出样例

输入 #1

输出 #1

说明/提示

**样例解释：**在开始的时候就直接走到

对于30%的数据，

对于另外30%的数据，

对于100%的数据， $n<=10^5,m<=5 imes10^5,T<=10^5n<=105,m<=5×105,T<=105$

数据保证所有时间在

注意：在任意一个

$题解：一开始忘加最后一个点，无穷大，就是说最后停在最后那个点不再移动，不然没法比较嗯。$

$其实难度还好，裸的spfa加一点点的小贪心就ok$

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1000003; 
const int oo=0x3f3f3f3f;
int cnt,n,m,s1,s2,x,y,z,T;
int head[N],dis[N],vis[N];
struct node{
    int to,next,w;
}e[N];
struct ycyc{
    int xx;
    int yy;
}f[N];
void add(int x,int y,int z){
    e[++cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt;
}

void spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s1);vis[s1]=1; dis[s1]=0;
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) { vis[v]=1; q.push(v);}
            }
        }
    }
}

bool cmp(ycyc p,ycyc q){
    return p.xx<q.xx;
}

int main(){
    freopen("4880.in","r",stdin);
    freopen("4880.out","w",stdout);
    scanf("%d %d %d %d",&n,&m,&s1,&s2);
    f[0].xx=0; f[0].yy=s2;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    spfa(); scanf("%d",&T);
    int ans=-1;
    for(int i=1;i<=T;i++)
        scanf("%d %d",&f[i].xx,&f[i].yy);
    f[++T].xx=oo; f[T].yy=0;
    sort(f,f+T+1,cmp);
    for(int i=0;i<=T;i++){
        if(dis[f[i].yy]<f[i+1].xx){
            cout<<max(dis[f[i].yy],f[i].xx)<<endl;
            return 0;
        }
    }
    //printf("%d
")
    return 0;
}