Submission #1336478
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
char c[300],s[2];
vector<int>E[300];
bool d[300][300],used[300];
string dp[300][301];
string INF(500,'z');
string dfs(int u,int k){
if(dp[u][k]!="")return dp[u][k];
string a=INF;
if(k==1){
a=c[u];return dp[u][k]=a;
}
used[u]=1;
for(int v:E[u]){
if(!used[v])a=min(a,dfs(v,k-1));
}
a+=c[u];
used[u]=0;
return dp[u][k]=a;
}
int main() {
int n,m,k;scanf("%d%d%d",&n,&m,&k);
rep(i,n){
scanf("%s",s);c[i]=s[0];
}
rep(i,m){
int a,b;scanf("%d%d",&a,&b);a--;b--;
d[b][a]=1;
}
rep(i,n)d[i][i]=1;
rep(k,n)rep(i,n)rep(j,n)d[i][j]=max((int)d[i][j],d[i][k]&d[k][j]);
rep(i,n)rep(j,n){
if(d[i][j]&&i!=j)E[i].push_back(j);
}
string ans=INF;
rep(i,n){
ans=min(ans,dfs(i,k));
}
if(ans==INF)puts("-1");
else cout<<ans<<endl;
}
Submission Info
Submission Time
2017-06-08 16:07:58+0900
Task
C - 有向グラフ
User
autumn_eel
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
877 Byte
Status
WA
Exec Time
653 ms
Memory
46976 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n,m,k;scanf("%d%d%d",&n,&m,&k);
^
./Main.cpp:28:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);c[i]=s[0];
^
./Main.cpp:31:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a,b;scanf("%d%d",&a,&b);a--;b--;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_manual01.txt, subtask1_manual02.txt, subtask1_manual03.txt, subtask1_manual04.txt, subtask1_manual05.txt, subtask1_manual06.txt, subtask1_manual07.txt, subtask1_manual08.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt, subtask1_special11.txt, subtask1_special12.txt, subtask1_special13.txt, subtask1_special14.txt, subtask1_special15.txt
Case Name
Status
Exec Time
Memory
subtask0_sample_01.txt
AC
2 ms
1024 KB
subtask0_sample_02.txt
AC
2 ms
1024 KB
subtask0_sample_03.txt
AC
2 ms
1024 KB
subtask0_sample_04.txt
AC
2 ms
1024 KB
subtask1_manual01.txt
AC
2 ms
1024 KB
subtask1_manual02.txt
AC
2 ms
1024 KB
subtask1_manual03.txt
AC
2 ms
1024 KB
subtask1_manual04.txt
AC
2 ms
1024 KB
subtask1_manual05.txt
AC
2 ms
1024 KB
subtask1_manual06.txt
AC
2 ms
1024 KB
subtask1_manual07.txt
AC
2 ms
1024 KB
subtask1_manual08.txt
AC
2 ms
1024 KB
subtask1_random01.txt
WA
235 ms
8320 KB
subtask1_random02.txt
WA
116 ms
3328 KB
subtask1_random03.txt
WA
270 ms
13696 KB
subtask1_random04.txt
WA
236 ms
7552 KB
subtask1_random05.txt
AC
32 ms
1664 KB
subtask1_special01.txt
WA
350 ms
16768 KB
subtask1_special02.txt
AC
43 ms
1536 KB
subtask1_special03.txt
AC
219 ms
8704 KB
subtask1_special04.txt
AC
391 ms
25216 KB
subtask1_special05.txt
AC
640 ms
46720 KB
subtask1_special06.txt
WA
281 ms
32256 KB
subtask1_special07.txt
WA
237 ms
20224 KB
subtask1_special08.txt
WA
284 ms
32256 KB
subtask1_special09.txt
WA
285 ms
32256 KB
subtask1_special10.txt
WA
282 ms
32256 KB
subtask1_special11.txt
WA
513 ms
46080 KB
subtask1_special12.txt
WA
385 ms
38400 KB
subtask1_special13.txt
WA
507 ms
45568 KB
subtask1_special14.txt
AC
32 ms
1024 KB
subtask1_special15.txt
AC
653 ms
46976 KB