Submission #19993959
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX=2e3+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int drc[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct edge{
int to,dis;
bool operator< (const edge& p) const{
return dis>p.dis;
}
};
vector<edge> v[MAX];
int n,m,k;
void Scan(){
int x,y,d;
edge e;
for(int i=0;i<m;++i){
scanf("%d%d%d",&x,&y,&d);
e.to=y; e.dis=d;
v[x].push_back(e);
}
}
int Dijkstra(const int s){
priority_queue<edge> q;
edge e;
e.to=s;
e.dis=0;
q.push(e);
char f[MAX]={0};
int dis[MAX]={0};
memset(dis,0x3f,sizeof(dis));
while(q.size()){
edge temp=q.top();
if(temp.to==s&&temp.dis!=0){
return temp.dis;
}
q.pop();
if(!f[temp.to]){
f[temp.to]=1;
int l=v[temp.to].size();
for(int i=0;i<l;++i){
e=v[temp.to][i];
e.to;
e.dis=temp.dis+e.dis;
if(e.dis<dis[e.to]){
dis[e.to]=e.dis;
q.push(e);
}
}
}
}
return -1;
}
void Solve(){
for(int i=1;i<=n;++i){
int k=Dijkstra(i);
printf("%d\n",k);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
Scan();
Solve();
for(int i=1;i<=n;++i){
v[i].clear();
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Come Back Quickly |
User |
YinChuanSheng |
Language |
C++ (Clang 10.0.0) |
Score |
500 |
Code Size |
1660 Byte |
Status |
AC |
Exec Time |
108 ms |
Memory |
3336 KB |
Compile Error
./Main.cpp:55:19: warning: expression result unused [-Wunused-value]
e.to;
~ ^~
./Main.cpp:13:11: warning: unused variable 'inf' [-Wunused-const-variable]
const int inf=0x3f3f3f3f;
^
./Main.cpp:14:11: warning: unused variable 'mod' [-Wunused-const-variable]
const int mod=1e9+7;
^
./Main.cpp:15:11: warning: unused variable 'drc' [-Wunused-const-variable]
const int drc[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
^
4 warnings generated.
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
almost_path_00.txt, almost_path_01.txt, almost_path_02.txt, almost_path_03.txt, almost_path_04.txt, almost_path_05.txt, almost_path_06.txt, almost_path_07.txt, almost_path_08.txt, almost_path_09.txt, handmade_00.txt, handmade_01.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, sample_01.txt, sample_02.txt, sample_03.txt, wide_00.txt |
Case Name |
Status |
Exec Time |
Memory |
almost_path_00.txt |
AC |
45 ms |
3176 KB |
almost_path_01.txt |
AC |
39 ms |
3192 KB |
almost_path_02.txt |
AC |
38 ms |
3332 KB |
almost_path_03.txt |
AC |
36 ms |
3128 KB |
almost_path_04.txt |
AC |
35 ms |
3184 KB |
almost_path_05.txt |
AC |
3 ms |
3296 KB |
almost_path_06.txt |
AC |
4 ms |
3208 KB |
almost_path_07.txt |
AC |
35 ms |
3156 KB |
almost_path_08.txt |
AC |
28 ms |
3300 KB |
almost_path_09.txt |
AC |
60 ms |
3128 KB |
handmade_00.txt |
AC |
2 ms |
3244 KB |
handmade_01.txt |
AC |
2 ms |
3056 KB |
random_00.txt |
AC |
9 ms |
3308 KB |
random_01.txt |
AC |
3 ms |
3092 KB |
random_02.txt |
AC |
11 ms |
3336 KB |
random_03.txt |
AC |
10 ms |
3188 KB |
random_04.txt |
AC |
9 ms |
3164 KB |
random_05.txt |
AC |
6 ms |
3092 KB |
random_06.txt |
AC |
5 ms |
3300 KB |
random_07.txt |
AC |
6 ms |
3092 KB |
random_08.txt |
AC |
9 ms |
3092 KB |
random_09.txt |
AC |
3 ms |
3112 KB |
random_10.txt |
AC |
3 ms |
3144 KB |
random_11.txt |
AC |
3 ms |
3148 KB |
random_12.txt |
AC |
4 ms |
3160 KB |
random_13.txt |
AC |
3 ms |
3164 KB |
random_14.txt |
AC |
3 ms |
3092 KB |
random_15.txt |
AC |
2 ms |
3120 KB |
random_16.txt |
AC |
6 ms |
3280 KB |
random_17.txt |
AC |
9 ms |
3176 KB |
random_18.txt |
AC |
3 ms |
3280 KB |
random_19.txt |
AC |
22 ms |
3084 KB |
random_20.txt |
AC |
15 ms |
3216 KB |
random_21.txt |
AC |
5 ms |
3168 KB |
random_22.txt |
AC |
22 ms |
3124 KB |
random_23.txt |
AC |
18 ms |
3160 KB |
random_24.txt |
AC |
31 ms |
3132 KB |
sample_01.txt |
AC |
2 ms |
3276 KB |
sample_02.txt |
AC |
2 ms |
3108 KB |
sample_03.txt |
AC |
2 ms |
3080 KB |
wide_00.txt |
AC |
108 ms |
3152 KB |