Submission #4065549


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define rep(i, a, b) for (auto (i) = (a); (i) < (b); (i)++)
#define rrep(i, a, b) for (auto (i) = (a); (i) > (b); (i)--)

#define aim_cpo do{ios::sync_with_stdio(false);\
cin.tie(nullptr);cout.precision(12);cout<<fixed;}while(0)

#define LOCAL_INPUT do{FILE *stream1;\
stream1=freopen("/Users/aim_cpo/CLionProjects/competitive/in.txt","r",stdin);\
if(stream1==nullptr)return 0;}while(0)
#define LOCAL_OUTPUT do{FILE *stream2;\
stream2 = freopen("out.txt", "w", stdout);\
if (stream2 == nullptr) return 0;}while(0)

#ifdef LOCAL_DEFINE
#define show(x) cerr << #x << " = " << (x) << endl
#define showV(v, n) do{\
for(int _i_t_e_=0; _i_t_e_<(n);_i_t_e_++)\
cerr<<"("<<_i_t_e_<<" = "<<(v)[_i_t_e_]<<") ";\
cerr<<endl;}while(0)
#define showA(a, n) do{\
for(int _i_t_e_=0;_i_t_e_<(n);_i_t_e_++)\
cerr<<"("<<_i_t_e_<<" = "<<(a)[_i_t_e_]<<") ";\
cerr<<endl;}while(0)
#define showA2(a, n, m) do{\
for(int _i_t_e_=0;_i_t_e_<(n);_i_t_e_++){\
for(int _i_t_e_2=0;_i_t_e_2<(m);_i_t_e_2++){\
cerr<<"("<<_i_t_e_<<", "<<_i_t_e_2<<" = "<<(a)[_i_t_e_][_i_t_e_2]<<") ";\
}cerr<<endl;}cerr<<endl;}while(0)
#else
#define show(x)
#define showV(v, n)
#define showA(a, n)
#define showA2(a, n, m)
#endif

typedef long long ll;
typedef unsigned long long ull;

constexpr const int INT_INF=0x3f3f3f3f; //1061109567
constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f; //4557430888798830399

template <typename T> bool chmin(T &a, T b){return a>b?(a=b,true):false;}
template <typename T> bool chmax(T &a, T b){return a<b?(a=b,true):false;}
template <typename T> void ln(T i, T n){cout<<(i==n-1?"\n":" ");}

// INT
#define GCD(a, b) __gcd(a, b)
template <typename T> T LCM(T a, T b) {return a / GCD(a, b) * b;}
template <typename T> T EXTGCD(T a, T b, T& x, T& y) {
  T d = a;
  if (b != 0) {d=EXTGCD(b,a%b,y,x);y-=(a/b)*x;}
  else x=1,y=0;
  return d;
}
template <typename T> bool is_prime(T a) {
  for(int i=2;i*i<=a;i++)if(a%i==0)return 1;
  return 0;
}

// MOD
ll MOD = 1000000000L + 7L;
#define add(a, b) ((a % MOD) + (b % MOD)) % MOD
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define sub(a, b) ((a % MOD) + MOD - (b % MOD)) % MOD
template <typename T> T mod_inverse(T a, T mod, bool prime){ // if mod is prime, "prime" is true.
  if(prime){
    T tmp=mod-2,now=a,res=1;while(tmp){if(tmp&1)res=mul(res,now);now=mul(now,now);tmp>>=1;}
    return res;
  }else{T x,y;EXTGCD(a,mod,x,y);return (mod+x%mod)%mod;}
}
#define divide(a, b) ((a % MOD) * (mod_inverse(b, MOD, true))) % MOD

//LLの数値をつかう時は最後にLをつける癖をつけよう
//
//  ┏┓┏┓ ┓ ┏┓
//  ┏┛┃┃ ┃ ┗┫
//  ┗┛┗┛ ┻ ┗┛
//
//   謹┃賀┃新┃年┃
//   ━┛━┛━┛━┛
//WWWWWWWWWWWWWWWWWWWWWW

int n, m;
vector <pair <int, int> > v[100001];
int d[100001];

int main() {
  aim_cpo; // インタラクティブのときは消すように.
#ifdef LOCAL_DEFINE
  LOCAL_INPUT; // インタラクティブのときは消すように.
//  LOCAL_OUTPUT; // ファイルに出力したいときのみ
  show(MOD);
#endif
  cin >> n >> m;
  rep(i, 0, m) {
    int from, to, c; cin >> from >> to >> c;
    from--; to--; c--;
    v[from].push_back(mp(to, c));
    v[to].push_back(mp(from, c));
  }
  fill(d, d + n, INT_INF);
  priority_queue<tuple<int, int, int> > q;
  q.push(mt(0, 0, -1));
  while (!q.empty()) {
    int now, cost, pre; tie(cost, now, pre) = q.top(); q.pop();
    cost *= -1;
    if (d[now] < cost) continue;
    d[now] = cost;
    rep(i, 0, (int)v[now].size()) {
      int next = v[now][i].fi;
      int cop = v[now][i].se;
      int nextcost = cost + (cop == pre ? 0 : 1);
      if (d[next] > nextcost) {
        d[next] = nextcost;
        q.push(mt(-nextcost, next, cop));
      }
    }
  }
  if (d[n - 1] == INT_INF) {
    cout << -1 << endl;
  } else {
    cout << d[n - 1] << endl;
  }
#ifdef  LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s." << endl;
#endif
  return 0;
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User aim_cpo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4278 Byte
Status WA
Exec Time 118 ms
Memory 10612 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 48
WA × 11
Set Name Test Cases
Sample
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt
Case Name Status Exec Time Memory
01.txt AC 3 ms 2560 KB
02.txt AC 49 ms 7040 KB
03.txt AC 118 ms 10108 KB
04.txt AC 82 ms 9216 KB
05.txt WA 105 ms 10108 KB
06.txt AC 40 ms 6144 KB
07.txt AC 58 ms 7168 KB
08.txt AC 103 ms 10492 KB
09.txt AC 60 ms 7168 KB
10.txt AC 59 ms 7168 KB
11.txt AC 76 ms 9016 KB
12.txt AC 43 ms 6520 KB
13.txt AC 58 ms 7804 KB
14.txt AC 80 ms 8956 KB
15.txt AC 73 ms 8684 KB
16.txt WA 80 ms 8980 KB
17.txt WA 76 ms 9336 KB
18.txt AC 53 ms 7292 KB
19.txt AC 75 ms 9588 KB
20.txt AC 82 ms 9988 KB
21.txt AC 78 ms 9128 KB
22.txt WA 77 ms 9336 KB
23.txt AC 83 ms 9340 KB
24.txt AC 73 ms 8700 KB
25.txt AC 43 ms 6648 KB
26.txt AC 59 ms 7804 KB
27.txt AC 73 ms 8320 KB
28.txt AC 73 ms 8684 KB
29.txt AC 75 ms 8664 KB
30.txt AC 74 ms 9336 KB
31.txt AC 54 ms 7292 KB
32.txt AC 74 ms 9588 KB
33.txt AC 77 ms 8780 KB
34.txt AC 75 ms 9016 KB
35.txt AC 43 ms 6648 KB
36.txt AC 59 ms 7800 KB
37.txt AC 78 ms 9720 KB
38.txt AC 79 ms 9892 KB
sample_01.txt AC 3 ms 2560 KB
sample_02.txt AC 3 ms 2560 KB
sample_03.txt AC 3 ms 2560 KB
w1.txt WA 83 ms 9952 KB
w10.txt AC 73 ms 8064 KB
w11.txt AC 47 ms 6492 KB
w12.txt AC 50 ms 6656 KB
w13.txt WA 54 ms 7040 KB
w14.txt AC 69 ms 8064 KB
w15.txt AC 43 ms 6744 KB
w16.txt AC 46 ms 6656 KB
w17.txt AC 56 ms 7040 KB
w18.txt WA 70 ms 8064 KB
w2.txt AC 80 ms 9436 KB
w3.txt WA 96 ms 10612 KB
w4.txt AC 94 ms 10484 KB
w5.txt AC 96 ms 10484 KB
w6.txt AC 92 ms 10484 KB
w7.txt WA 49 ms 6452 KB
w8.txt WA 52 ms 6528 KB
w9.txt WA 59 ms 7040 KB