Submission #3229156
Source Code Expand
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 200005;
struct Edge{
int to,next,w;
}e[MAXN<<3];
struct E{
int u,v,c;
bool operator < (const E &b)const
{
return c<b.c;
}
}t[MAXN<<1];
int head[MAXN<<3],n,m,fa[MAXN],id[MAXN],sz;
bool vis[MAXN<<3];
int getan(int x)
{
return x==fa[x]?x:fa[x]=getan(fa[x]);
}
int cnt=0;
inline void insert(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt,e[cnt].w=w;
}
inline void work(int l,int r)
{
for(int i=l;i<=r;++i){
vis[t[i].u]=vis[t[i].v]=id[t[i].u]=id[t[i].v]=0;
fa[t[i].u]=t[i].u;
fa[t[i].v]=t[i].v;
}
for(int i=l,x,y;i<=r;++i)
x=getan(t[i].u),y=getan(t[i].v),fa[x]=y;
for(int i=l,x,y;i<=r;++i){
x=getan(t[i].u),y=getan(t[i].v);
if(!vis[t[i].u]){
if(!id[x])id[x]=++sz;
insert(t[i].u,id[x],0);
insert(id[x],t[i].u,1);
vis[t[i].u]=1;
}
if(!vis[t[i].v]){
if(!id[y])id[y]=++sz;
insert(t[i].v,id[y],0);
insert(id[y],t[i].v,1);
vis[t[i].v]=1;
}
}
}
struct Node{
int x,v;
bool operator < (const Node &b)const
{
return v>b.v;
}
};
priority_queue<Node>q;
int d[MAXN<<3];
inline void dij()
{
memset(vis,0,sizeof(vis));
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push((Node){1,0});
while(!q.empty()){
Node x=q.top();
q.pop();
int u=x.x;
if(vis[u])continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
q.push((Node){v,d[v]});
}
}
}
cout<<(d[n]==0x3f3f3f3f?-1:d[n])<<endl;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].c);
}
sz=n;
sort(t+1,t+m+1);
int p=1;
while(p<=m){
int r=p;
while(t[r+1].c==t[r].c)++r;
work(p,r);
++p;
}
dij();
return 0;
}
Submission Info
Submission Time
2018-09-20 15:12:27+0900
Task
E - Snuke's Subway Trip
User
DFPMTS
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1897 Byte
Status
RE
Exec Time
3163 ms
Memory
38264 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:89:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].c);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 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
5 ms
14592 KB
02.txt
RE
188 ms
29056 KB
03.txt
AC
127 ms
29564 KB
04.txt
RE
169 ms
31104 KB
05.txt
RE
186 ms
31104 KB
06.txt
RE
148 ms
31104 KB
07.txt
RE
154 ms
31104 KB
08.txt
AC
128 ms
29564 KB
09.txt
RE
145 ms
31104 KB
10.txt
RE
151 ms
31104 KB
11.txt
RE
235 ms
29056 KB
12.txt
TLE
3155 ms
28928 KB
13.txt
RE
259 ms
29056 KB
14.txt
RE
238 ms
29056 KB
15.txt
RE
295 ms
29056 KB
16.txt
RE
252 ms
29056 KB
17.txt
RE
224 ms
29056 KB
18.txt
RE
413 ms
29056 KB
19.txt
RE
247 ms
29056 KB
20.txt
RE
202 ms
29056 KB
21.txt
AC
137 ms
38264 KB
22.txt
RE
181 ms
29056 KB
23.txt
RE
192 ms
31104 KB
24.txt
RE
199 ms
29056 KB
25.txt
RE
1464 ms
29056 KB
26.txt
RE
248 ms
29056 KB
27.txt
RE
186 ms
29056 KB
28.txt
RE
199 ms
29056 KB
29.txt
RE
191 ms
29056 KB
30.txt
RE
209 ms
29056 KB
31.txt
RE
224 ms
29056 KB
32.txt
RE
241 ms
29056 KB
33.txt
RE
190 ms
29056 KB
34.txt
RE
226 ms
29056 KB
35.txt
TLE
3155 ms
20736 KB
36.txt
RE
353 ms
29056 KB
37.txt
RE
230 ms
29056 KB
38.txt
RE
228 ms
29056 KB
sample_01.txt
AC
5 ms
14592 KB
sample_02.txt
AC
5 ms
14592 KB
sample_03.txt
AC
4 ms
10496 KB
w1.txt
RE
257 ms
29056 KB
w10.txt
AC
77 ms
28928 KB
w11.txt
RE
820 ms
29056 KB
w12.txt
RE
226 ms
29056 KB
w13.txt
RE
173 ms
31104 KB
w14.txt
RE
167 ms
31104 KB
w15.txt
TLE
3155 ms
12544 KB
w16.txt
TLE
3163 ms
29056 KB
w17.txt
RE
514 ms
29056 KB
w18.txt
RE
228 ms
29056 KB
w2.txt
RE
255 ms
29056 KB
w3.txt
RE
207 ms
31104 KB
w4.txt
RE
269 ms
29056 KB
w5.txt
AC
114 ms
30072 KB
w6.txt
RE
186 ms
31104 KB
w7.txt
AC
86 ms
27516 KB
w8.txt
AC
86 ms
28928 KB
w9.txt
AC
91 ms
28928 KB