Submission #3229102
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];
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<<1];
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:01:34+0900
Task
E - Snuke's Subway Trip
User
DFPMTS
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1894 Byte
Status
RE
Exec Time
3155 ms
Memory
8576 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
5504 KB
02.txt
RE
156 ms
7552 KB
03.txt
RE
163 ms
8576 KB
04.txt
RE
155 ms
8576 KB
05.txt
RE
155 ms
8576 KB
06.txt
RE
128 ms
8576 KB
07.txt
RE
131 ms
8576 KB
08.txt
RE
163 ms
8576 KB
09.txt
RE
132 ms
8576 KB
10.txt
RE
132 ms
8576 KB
11.txt
RE
167 ms
8576 KB
12.txt
RE
946 ms
7552 KB
13.txt
RE
170 ms
7808 KB
14.txt
RE
169 ms
8576 KB
15.txt
RE
178 ms
8576 KB
16.txt
RE
175 ms
8576 KB
17.txt
RE
164 ms
8576 KB
18.txt
RE
209 ms
7680 KB
19.txt
RE
174 ms
8576 KB
20.txt
RE
158 ms
8576 KB
21.txt
RE
157 ms
8576 KB
22.txt
RE
156 ms
8576 KB
23.txt
RE
158 ms
8576 KB
24.txt
RE
156 ms
8576 KB
25.txt
RE
469 ms
7552 KB
26.txt
RE
169 ms
7808 KB
27.txt
RE
153 ms
8576 KB
28.txt
RE
154 ms
8576 KB
29.txt
RE
154 ms
8576 KB
30.txt
RE
160 ms
8576 KB
31.txt
RE
162 ms
7680 KB
32.txt
RE
171 ms
8576 KB
33.txt
RE
155 ms
8576 KB
34.txt
RE
166 ms
7552 KB
35.txt
RE
950 ms
7552 KB
36.txt
RE
195 ms
7680 KB
37.txt
RE
167 ms
7680 KB
38.txt
RE
165 ms
7552 KB
sample_01.txt
AC
3 ms
5504 KB
sample_02.txt
AC
2 ms
5504 KB
sample_03.txt
AC
1 ms
1408 KB
w1.txt
RE
179 ms
8576 KB
w10.txt
RE
162 ms
7808 KB
w11.txt
RE
321 ms
7680 KB
w12.txt
RE
173 ms
7552 KB
w13.txt
RE
154 ms
7680 KB
w14.txt
RE
153 ms
7808 KB
w15.txt
TLE
3155 ms
6400 KB
w16.txt
RE
938 ms
7552 KB
w17.txt
RE
237 ms
7552 KB
w18.txt
RE
168 ms
7808 KB
w2.txt
RE
178 ms
8576 KB
w3.txt
RE
165 ms
8576 KB
w4.txt
RE
174 ms
8576 KB
w5.txt
RE
164 ms
8576 KB
w6.txt
RE
158 ms
8576 KB
w7.txt
RE
155 ms
7680 KB
w8.txt
RE
156 ms
7680 KB
w9.txt
RE
159 ms
7680 KB