codeforce每日一题链接
每日一题题解视频
题目链接
题目分数：1700
题目描述
输入$n(2<n≤1e5) m(0≤m≤1e5)$表示一个$n$点$m$边的无向图（节点编号从$1$开始)。然后输入$m$条边，每条边包含$3$个数$a，b， c(1<c≤1e4)$，表示有一条边权为$c$的无向边连接$a$和$b$.保证无自环、无重边。然后输入$n$行，每行第一个数$k$表示数组$t[i]$的长度，然后输入数组$t[i]$。数组$t[i]$是一个严格递增序列，$0≤t[i] [j]<1e9$。所有$k$之和$≤1e5$。
初始时间为$0$。你从$1$出发，要去$n$。如果你在点$i$，但是当前时间在数组$t[i]$中，那么你必须等待$1$秒。如果下一秒仍然在$t[i]$中，那么继续等待$1$秒。依此类推。输出到达$n$的最早时间。如果无法到达$n$，输出$-1$。
样例
输入样例1
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
输出样例1
7
输入样例2
3 1
1 2 3
0
1 3
0
输出样例2
-1
算法
(spfa) $O(m)$
这道题我们先预处理一下，对于每一个点，我们创建一个$map$，如果当前时间需要加$1$的话，可以从$map$中$o(1)$的找到，可以从后向前循环，假设当前点会加$1$到$t$，那么对于它的前一个点，如果前一个点的时间等于现在点的时间减$1$，那么前一个点的也会一直加$1$到$t$，否则为前一个的时间加$1$，并将$t$动态修改。
那么我们就可以选用一个最短路算法了，这里我用的是$spfa$($dijkstra$在下面)，在修改时间时，要在$map$中查询一下当前时间能不能走。注意，对于终点$n$，我们是不需要看时间的限制的，因为我们不需要再往下走了。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5+10, M = N * 2, INF = 1e18;
int n, m;
map<int, int> g[N];
vector<int> f[N];
int e[M], ne[M], w[M], h[N], idx;
LL dist[N];
bool st[N];
inline void add(int a, int b, int c)
{
e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}
inline int spfa()
{
for(int i=1;i<=n;i++) dist[i] = INF;
dist[1] = g[1][0];
queue<int> q;
q.push(1);
while(q.size())
{
auto u = q.front();
q.pop();
st[u] = false;
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
int t = dist[u] + w[i];
if(j!=n && g[j].count(t)) t = g[j][t];
if(dist[j]>t){
dist[j] = t;
if(!st[j]){
st[j] = true;
q.push(j);
}
}
}
}
return dist[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(h, -1, sizeof h);
cin>>n>>m;
while(m--)
{
int a, b, c;
cin>>a>>b>>c;
add(a, b, c), add(b, a, c);
}
for(int i=1;i<=n;i++){
int k;
cin>>k;
if(!k) continue;
for(int j=0;j<k;j++){
int x;
cin>>x;
f[i].pd(x);
}
int t = f[i][k-1] + 1;
for(int j=f[i].size()-1;j>=0;j--)
{
if(j!=f[i].size()-1 && f[i][j]!=f[i][j+1]-1) t = f[i][j] + 1;
g[i][f[i][j]] = t;
}
}
LL d = spfa();
if(d>=INF/2) cout<<-1<<endl;
else cout<<d<<endl;
return 0;
}
算法
(dijkstra) $O(n*log(m))$
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5+10, M = N * 2, INF = 1e18;
int n, m;
map<int, int> g[N];
vector<int> f[N];
int e[M], ne[M], w[M], h[N], idx;
LL dist[N];
bool st[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto add = [](int a, int b, int c){
e[idx]=b, ne[idx]=h[a], w[idx]=c, h[a]=idx++;
};
memset(h, -1, sizeof h);
cin>>n>>m;
while(m--)
{
int a, b, c;
cin>>a>>b>>c;
add(a, b, c), add(b, a, c);
}
for(int i=1;i<=n;i++){
int k;
cin>>k;
if(!k) continue;
for(int j=0;j<k;j++){
int x;
cin>>x;
f[i].pd(x);
}
int t = f[i][k-1] + 1;
for(int j=f[i].size()-1;j>=0;j--)
{
if(j!=f[i].size()-1 && f[i][j]!=f[i][j+1]-1) t = f[i][j] + 1;
g[i][f[i][j]] = t;
}
}
auto dijkstra = [](){
for(int i=1;i<=n;i++) dist[i] = INF;
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[1] = g[1][0];
heap.push({g[1][0], 1});
while(heap.size())
{
auto p = heap.top();
heap.pop();
int u = p.se;
if(st[u]) continue;
st[u] = true;
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
int t = dist[u] + w[i];
if(j!=n && g[j].count(t)) t = g[j][t];
if(dist[j]>t){
dist[j] = t;
heap.push({dist[j], j});
}
}
}
return dist[n];
};
LL d = dijkstra();
if(d>=INF/2) cout<<-1<<endl;
else cout<<d<<endl;
return 0;
}