Submission #3229135
Source Code Expand
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
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:08:46+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
3155 ms
Memory
17792 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
4 ms
10496 KB
02.txt
RE
678 ms
17792 KB
03.txt
RE
169 ms
17792 KB
04.txt
RE
160 ms
17792 KB
05.txt
RE
167 ms
17792 KB
06.txt
RE
137 ms
17792 KB
07.txt
RE
138 ms
17792 KB
08.txt
RE
170 ms
17792 KB
09.txt
RE
137 ms
17792 KB
10.txt
RE
136 ms
17792 KB
11.txt
RE
189 ms
17792 KB
12.txt
RE
1756 ms
17792 KB
13.txt
RE
201 ms
17792 KB
14.txt
RE
193 ms
17792 KB
15.txt
RE
218 ms
17792 KB
16.txt
RE
201 ms
17792 KB
17.txt
RE
186 ms
17792 KB
18.txt
RE
277 ms
17792 KB
19.txt
RE
199 ms
17792 KB
20.txt
RE
174 ms
17792 KB
21.txt
RE
160 ms
17792 KB
22.txt
RE
165 ms
17792 KB
23.txt
RE
170 ms
17792 KB
24.txt
RE
170 ms
17792 KB
25.txt
RE
798 ms
17792 KB
26.txt
RE
194 ms
17792 KB
27.txt
RE
165 ms
17792 KB
28.txt
RE
172 ms
17792 KB
29.txt
RE
167 ms
17792 KB
30.txt
RE
178 ms
17792 KB
31.txt
RE
185 ms
17792 KB
32.txt
RE
197 ms
17792 KB
33.txt
RE
166 ms
17792 KB
34.txt
RE
186 ms
17792 KB
35.txt
TLE
3155 ms
17408 KB
36.txt
RE
248 ms
17792 KB
37.txt
RE
189 ms
17792 KB
38.txt
RE
189 ms
17792 KB
sample_01.txt
AC
4 ms
10496 KB
sample_02.txt
AC
4 ms
10496 KB
sample_03.txt
AC
3 ms
6400 KB
w1.txt
RE
207 ms
17792 KB
w10.txt
RE
166 ms
17792 KB
w11.txt
RE
484 ms
17792 KB
w12.txt
RE
188 ms
17792 KB
w13.txt
RE
160 ms
17792 KB
w14.txt
RE
158 ms
17792 KB
w15.txt
TLE
3155 ms
10496 KB
w16.txt
RE
1721 ms
17792 KB
w17.txt
RE
329 ms
17792 KB
w18.txt
RE
187 ms
17792 KB
w2.txt
RE
204 ms
17792 KB
w3.txt
RE
177 ms
17792 KB
w4.txt
RE
212 ms
17792 KB
w5.txt
RE
167 ms
17792 KB
w6.txt
RE
167 ms
17792 KB
w7.txt
RE
157 ms
17792 KB
w8.txt
RE
160 ms
17792 KB
w9.txt
RE
161 ms
17792 KB