Submission #3229106
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<<2];
struct E{
int u,v,c;
bool operator < (const E &b)const
{
return c<b.c;
}
}t[MAXN<<1];
int head[MAXN<<2],n,m,fa[MAXN],id[MAXN],sz;
bool vis[MAXN<<2];
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<<2];
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:03:21+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
9856 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
3 ms
8320 KB
02.txt
RE
672 ms
9600 KB
03.txt
RE
171 ms
9728 KB
04.txt
RE
159 ms
9728 KB
05.txt
RE
160 ms
9728 KB
06.txt
RE
135 ms
9728 KB
07.txt
RE
137 ms
9728 KB
08.txt
RE
168 ms
9728 KB
09.txt
RE
135 ms
9728 KB
10.txt
RE
136 ms
9728 KB
11.txt
RE
173 ms
9728 KB
12.txt
RE
954 ms
9472 KB
13.txt
RE
176 ms
9600 KB
14.txt
RE
180 ms
9728 KB
15.txt
RE
194 ms
9728 KB
16.txt
RE
179 ms
9728 KB
17.txt
RE
171 ms
9728 KB
18.txt
RE
214 ms
9600 KB
19.txt
RE
183 ms
9728 KB
20.txt
RE
167 ms
9728 KB
21.txt
RE
163 ms
9728 KB
22.txt
RE
161 ms
9728 KB
23.txt
RE
290 ms
9728 KB
24.txt
RE
161 ms
9728 KB
25.txt
RE
475 ms
9472 KB
26.txt
RE
171 ms
9600 KB
27.txt
RE
158 ms
9728 KB
28.txt
RE
161 ms
9728 KB
29.txt
RE
163 ms
9728 KB
30.txt
RE
164 ms
9728 KB
31.txt
RE
164 ms
9728 KB
32.txt
RE
177 ms
9728 KB
33.txt
RE
162 ms
9728 KB
34.txt
RE
169 ms
9600 KB
35.txt
RE
1754 ms
9472 KB
36.txt
RE
200 ms
9600 KB
37.txt
RE
173 ms
9600 KB
38.txt
RE
171 ms
9600 KB
sample_01.txt
AC
3 ms
8320 KB
sample_02.txt
AC
3 ms
8320 KB
sample_03.txt
AC
2 ms
4224 KB
w1.txt
RE
185 ms
9728 KB
w10.txt
RE
168 ms
9600 KB
w11.txt
RE
318 ms
9472 KB
w12.txt
RE
177 ms
9600 KB
w13.txt
RE
158 ms
9600 KB
w14.txt
RE
158 ms
9600 KB
w15.txt
TLE
3155 ms
8448 KB
w16.txt
RE
942 ms
9600 KB
w17.txt
RE
241 ms
9600 KB
w18.txt
RE
172 ms
9600 KB
w2.txt
RE
185 ms
9728 KB
w3.txt
RE
168 ms
9728 KB
w4.txt
RE
192 ms
9856 KB
w5.txt
RE
169 ms
9728 KB
w6.txt
RE
166 ms
9728 KB
w7.txt
RE
160 ms
9472 KB
w8.txt
RE
162 ms
9472 KB
w9.txt
RE
163 ms
9600 KB