題目連結:
https://www.luogu.org/problem/P4880
思路:
1:先跑spfa求出從開始節點到每一個節點的最短路
2:把所有時刻的移動按時間從小到大排序,然後暴力枚舉,如果到不了就枚舉下一個點
注意:
1:這道題目不難,但是自己反複送出10多遍,花了4個小時,就是因為自己讀題不仔細,或者說是對題目給出的資料範圍不敏感,題目中的 對于另外30%的資料,T=0,這句話是3個測試點,就是一句簡單的if判斷,自己忽略了,導緻自己這3個測試點一直wa
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+1,inf=0x3f3f3f3f;
vector<pair<int,int> >e[maxn];
int n,m,s,t,f,a,b,c,d[maxn],ing[maxn];
struct point
{
int time;
int x;
}p[maxn];
bool cmp(const point &a,const point &b)
{
return a.time<b.time;
}
inline void spfa()
{
memset(d,inf,sizeof(d));
memset(ing,0,sizeof(ing));
queue<int>q;
q.push(s);
d[s]=0;
ing[s]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing[now]=0;
for(int i=0;i<e[now].size();i++)
{
int v=e[now][i].first;
if(d[v]>d[now]+e[now][i].second)
{
d[v]=d[now]+e[now][i].second;
if(ing[v])
continue;
q.push(v);
ing[v]=1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[a].push_back(make_pair(b,c));
e[b].push_back(make_pair(a,c));
}
spfa();
scanf("%d",&f);
if(f==0)
{
printf("%d",d[t]);
return 0;
}
for(int i=1;i<=f;i++)
{
scanf("%d%d",&p[i].time,&p[i].x);
}
sort(p+1,p+f+1,cmp);
if(d[t]<p[1].time)
{
printf("%d",d[t]);
return 0;
}
for(int i=1;i<f;i++)
{
if(d[p[i].x]<p[i+1].time)
{
printf("%d\n",max(p[i].time,d[p[i].x]));
return 0;
}
}
printf("%d\n",max(d[p[f].x],p[f].time));
return 0;
}