一、題目
點此看題
二、解法
首先請明確兩點：可以往回走！ d p dp dp貪心死活想不出來的時候可以考慮下圖論，思路要打開！
其實這道題如果用最短路的話就比較好想，我們的目的是讓每個點向相鄰的點轉移（這樣可以兼顧回退、等待、前進），但是我們要知道時間，怎么辦？我們知道時間的目的是為了確定閘門的關閉，既然不能知道具體的時間，我們就通過閘門的關閉時間段來劃分時間段，夾在兩個之間的就當做一個可通行的狀態，通過最短路可求出到達這個狀態的最小時間，狀態的編號就用夾住它的前面關閉時間段的編號，狀態數是 O ( n + m ) O(n+m) O(n+m)的，
建圖怎么辦？不難發現是邊數 O ( m ) O(m) O(m)的，因為只有相鄰點之間的可通行時間段相交的時候才會產生邊，但是如果你不注意建邊的方式就很容易炸成部分分，一種很好的方法就是在 d j dj dj的時候直接跑，由于訪問的左端點是單增的（指的是我們到達這個狀態的最小時間），那么如果一段區間和它不相交，那么以后都不相交，維護每個位置的指標即可，
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 100005;
const int inf = 0x3f3f3f3f;
int read()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();
return num*flag;
}
int n,m,pos[M];
vector<int> dis[M];
struct range
{
int l,r;
bool operator < (const range &b) const
{
return l<b.l;
}
};vector<range> v[M];
struct node
{
int x,id,l,r;
bool operator < (const node &b) const
{
return l>b.l;
}
};
int dijk()
{
for(int i=0;i<=n+1;i++)
{
int len=v[i].size();
dis[i].resize(len);
for(int j=0;j<len;j++)
dis[i][j]=inf;
v[i].push_back(range{inf,inf});
}
priority_queue<node> q;
q.push(node{0,0,0,inf-1});
dis[0][0]=0;
while(!q.empty())
{
node t=q.top();q.pop();
if(dis[t.x][t.id]<t.l) break;
if(t.x==n+1) return t.l;
int nl=t.l+1,nr=t.r+1;
for(int p=t.x-1;p<=t.x+1;p+=2)
{
if(p<0) continue;
while(v[p][pos[p]+1].l<=nl) pos[p]++;
int len=v[p].size();
for(int i=pos[p];i+1<len;i++)
{
if(v[p][i].r>=nr) break;
int cost=max(nl,v[p][i].r+1);
if(cost<dis[p][i])
{
dis[p][i]=cost;
q.push(node{p,i,cost,v[p][i+1].l-1});
}
}
}
}
return 'n'+'m'+'s'+'l';
}
signed main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),c=read();
v[a].push_back(range{b,c});
}
for(int i=0;i<=n+1;i++)
v[i].push_back(range{-1,-1});
for(int i=1;i<=n;i++)
sort(v[i].begin(),v[i].end());
printf("%d\n",dijk());
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/186119.html
標籤：其他
上一篇：尋找幸運數字小游戲
下一篇：題解——二叉樹的基本操作