侯瑞哲的博客

Ruizhe's Blog

0%

Egor in the Republic of Dagestan

发表于 Valine：

题意：

给出n个点和m条边的有向图，每条边的长度为1，有一个属性由0或1表示，现在需要给每个节点赋值，使得：

  1. 如果点u的权值为0，则u只能走（u，v）且这条边的属性为0的边。
  2. 如果点u的权值为1，则u只能走（u，v）且这条边的属性为1的边。

问如何赋值能让点1到点n的最短路径最大，输出一种构造方案。

思路：

这是一道dp题。

首先要先去除自环，因为要走最短路，这个肯定没有意义。

设dp_i,col表示第i个点涂上col这个颜色走到终点最短路最长是多少。

转移也非常好想：dp_i_col = min{max(dp_j,0，dp_j,1) + 1}，（edge{i, j, col ∈ E}

肯定是小的更新大的，所以最短路转移就好了。

另外，由于dp_j,0与dp_j,1取了一个max，所以如果用j来更新i的话，必须是第二个出现的。我们可以记录一个cnt。

初始化dp_n,0 = dp_n,1 = 0。

答案 = max(dp_1,0，dp_1,1)。

最后考虑第 i 个点。

  1. dp_i,0 > dp_i,1，col_i = 0
  2. dp_i,0 < dp_i,1，col_i = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
{By GWj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=5e5+20;
vector<pair<int,bool > > g[MAXN];
void add_edge(int u,int v,int col){
   if(u==v) return ;
   g[v].PB(II(u,col));
}
int n,m;
int dp[MAXN][2];
int cnt[MAXN];
int main(){
    fastio;
   R2(n,m);
  rb(i,1,m){
       int u,v,c;
       cin>>u>>v>>c;
     add_edge(u,v,c); 
 } 
   memset(dp,63,sizeof(dp));
  dp[n][0]=dp[n][1]=0;
  priority_queue<pair<int,mp> ,vector<pair<int,mp> > ,greater<pair<int,mp> > > q;
  q.push(II(0,II(n,0)));
    q.push(II(0,II(n,1)));
    while(!q.empty()){
      pair<int,mp> now=q.top();
        q.pop();
      int i,j;
     i=now.SEC.FIR;
        j=now.SEC.SEC;
        if(dp[i][j]!=now.FIR) continue;
     cnt[i]++;
     if(cnt[i]==1) continue;
     for(auto it:g[i]){
         if(dp[it.FIR][it.SEC]>dp[i][j]+1){
               dp[it.FIR][it.SEC]=dp[i][j]+1;
                q.push(II(dp[it.FIR][it.SEC],II(it.FIR,it.SEC)));
         }
        }
    }
    cout<<(max(dp[1][0],dp[1][1])!=INF? max(dp[1][0],dp[1][1]):-1)<<endl;
 rb(i,1,n){
       cout<<(dp[i][1]>dp[i][0]? 1:0);
    }cout<<endl;
   return 0;
}