Submission #4065786
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":" ");}
template <typename T, typename S>
ostream &operator<<(ostream &out,const pair<T, S> &pair1){
out<<'('<<pair1.fi<<", "<<pair1.se<<')';return out;}
// 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[512345];
ll d[512345];
int EdgeNum = 100000;
map <pair<int, int> , int> map1;
map <int, pair<int, int> > map2;
void AddEdge(int a, int b, int c) {
if (map1.find(mp(a, c)) == map1.end()) {
map2[EdgeNum] = mp(a, c);
map1[mp(a, c)] = EdgeNum++;
}
if (map1.find(mp(b, c)) == map1.end()) {
map2[EdgeNum] = mp(b, c);
map1[mp(b, c)] = EdgeNum++;
}
v[map1[mp(a, c)]].emplace_back(a, 1);
v[a].emplace_back(map1[mp(a, c)], 1);
v[map1[mp(a, c)]].emplace_back(map1[mp(b, c)], 0);
v[map1[mp(b, c)]].emplace_back(map1[mp(a, c)], 0);
v[map1[mp(b, c)]].emplace_back(b, 1);
v[b].emplace_back(map1[mp(b, c)], 1);
}
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--;
AddEdge(from, to, c);
}
fill(d, d + 512345, LL_INF);
priority_queue<pair<ll, int> > q;
q.push(mp(0, 0));
d[0] = 0;
while (!q.empty()) {
int now = q.top().se; ll cost = -q.top().fi; q.pop();
if (now < n) show(now);
else show(map2[now]);
show(cost);
if (d[now] < cost) continue;
rep(i, 0, (int)v[now].size()) {
int next = v[now][i].fi;
ll nextcost = cost + v[now][i].se;
if (d[next] > nextcost) {
d[next] = nextcost;
q.push(mp(-nextcost, next));
}
}
}
if (d[n - 1] == LL_INF) cout << -1 << endl;
else {
assert(d[n - 1] % 2 == 0);
cout << d[n - 1] / 2 << 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 |
600 |
Code Size |
5035 Byte |
Status |
AC |
Exec Time |
1083 ms |
Memory |
86516 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
AC
|
|
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 |
8 ms |
16256 KB |
02.txt |
AC |
630 ms |
45820 KB |
03.txt |
AC |
1083 ms |
86516 KB |
04.txt |
AC |
914 ms |
83968 KB |
05.txt |
AC |
955 ms |
69364 KB |
06.txt |
AC |
366 ms |
48640 KB |
07.txt |
AC |
432 ms |
50048 KB |
08.txt |
AC |
1020 ms |
86516 KB |
09.txt |
AC |
481 ms |
54784 KB |
10.txt |
AC |
475 ms |
54656 KB |
11.txt |
AC |
536 ms |
52212 KB |
12.txt |
AC |
148 ms |
28904 KB |
13.txt |
AC |
356 ms |
39408 KB |
14.txt |
AC |
478 ms |
51576 KB |
15.txt |
AC |
389 ms |
43636 KB |
16.txt |
AC |
455 ms |
47880 KB |
17.txt |
AC |
529 ms |
52976 KB |
18.txt |
AC |
246 ms |
33268 KB |
19.txt |
AC |
454 ms |
47708 KB |
20.txt |
AC |
595 ms |
55924 KB |
21.txt |
AC |
874 ms |
86256 KB |
22.txt |
AC |
587 ms |
58740 KB |
23.txt |
AC |
705 ms |
66932 KB |
24.txt |
AC |
537 ms |
53752 KB |
25.txt |
AC |
139 ms |
28020 KB |
26.txt |
AC |
319 ms |
39156 KB |
27.txt |
AC |
503 ms |
57592 KB |
28.txt |
AC |
533 ms |
55668 KB |
29.txt |
AC |
559 ms |
56948 KB |
30.txt |
AC |
564 ms |
53364 KB |
31.txt |
AC |
329 ms |
40184 KB |
32.txt |
AC |
455 ms |
47600 KB |
33.txt |
AC |
579 ms |
57720 KB |
34.txt |
AC |
462 ms |
43900 KB |
35.txt |
AC |
126 ms |
28404 KB |
36.txt |
AC |
251 ms |
33144 KB |
37.txt |
AC |
454 ms |
45560 KB |
38.txt |
AC |
423 ms |
43892 KB |
sample_01.txt |
AC |
8 ms |
16256 KB |
sample_02.txt |
AC |
8 ms |
16256 KB |
sample_03.txt |
AC |
8 ms |
16256 KB |
w1.txt |
AC |
490 ms |
48040 KB |
w10.txt |
AC |
906 ms |
84096 KB |
w11.txt |
AC |
221 ms |
28620 KB |
w12.txt |
AC |
355 ms |
33536 KB |
w13.txt |
AC |
653 ms |
52480 KB |
w14.txt |
AC |
861 ms |
78720 KB |
w15.txt |
AC |
90 ms |
28752 KB |
w16.txt |
AC |
210 ms |
29056 KB |
w17.txt |
AC |
305 ms |
31232 KB |
w18.txt |
AC |
506 ms |
41728 KB |
w2.txt |
AC |
453 ms |
47772 KB |
w3.txt |
AC |
634 ms |
58960 KB |
w4.txt |
AC |
510 ms |
47856 KB |
w5.txt |
AC |
956 ms |
85620 KB |
w6.txt |
AC |
820 ms |
69492 KB |
w7.txt |
AC |
959 ms |
82500 KB |
w8.txt |
AC |
1019 ms |
82176 KB |
w9.txt |
AC |
878 ms |
82944 KB |