QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #152720 | #6645. 百合 | rsj | Compile Error | / | / | C++14 | 2.4kb | 2023-08-28 18:23:58 | 2023-08-28 18:23:58 |
Judging History
answer
#include <bits/stdc++.h>
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
using ll = long long;
const int N = 140010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge {
int to,w;
edge *nex;
}*head[N];
priority_queue<pair<ll,int>> q;
ll dis[N];
int vis[N],k;
void add(int u,int v,int w) {
edge *cur=new edge;
cur->to=v;
cur->w=w;
cur->nex=head[u];
head[u]=cur;
}
void spfa() { // reset dis
memset(vis,0,sizeof(vis));
for(int i=0;i<(1<<k);i++) if(dis[i]<INF) q.push(make_pair(-dis[i],i));
while(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge *cur=head[u];cur;cur=cur->nex) {
if(dis[cur->to]>dis[u]+cur->w) {
dis[cur->to]=dis[u]+cur->w;
q.push(make_pair(-dis[cur->to],cur->to));
}
}
}
}
ll f[N][18];
int a[18];
void conv() {
int i,j,p;
memset(f,0x3f,sizeof(f));
for(i=0;i<(1<<k);i++) f[i][0]=dis[i];
for(j=0;j<k;j++) for(p=k;p>=1;p--) for(i=0;i<(1<<k);i++) f[i][p]=min(f[i][p],f[i^(1<<j)][p-1]);
for(i=0;i<(1<<k);i++) for(p=k;p>=1;p--) dis[i]=min(dis[i],f[i][p]+a[p]);
}
void debug() {
for(int i=0;i<(1<<k);i++) if(dis[i]<INF) cout<<dis[i]<<" "; else cout<<"INF ";
cout<<endl;
}
signed main() {
//freopen("1.in","r",stdin);
int m,s,i,u,v,w;
fin>>k>>m>>s;
for(i=1;i<=k;i++) fin>>a[i];
for(i=1;i<=m;i++) fin>>u>>v>>w,add(u,v,w),add(v,u,w);
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
for(i=0;i<=k;i++) {
conv();
//debug();
spfa();
//debug();
}
for(i=0;i<(1<<k);i++) fout<<dis[i]<<' ';
return 0;
}
Details
answer.code:30:1: error: ‘priority_queue’ does not name a type
30 | priority_queue<pair<ll,int>> q;
| ^~~~~~~~~~~~~~
answer.code: In function ‘void spfa()’:
answer.code:42:50: error: ‘q’ was not declared in this scope
42 | for(int i=0;i<(1<<k);i++) if(dis[i]<INF) q.push(make_pair(-dis[i],i));
| ^
answer.code:42:57: error: ‘make_pair’ was not declared in this scope; did you mean ‘std::make_pair’?
42 | for(int i=0;i<(1<<k);i++) if(dis[i]<INF) q.push(make_pair(-dis[i],i));
| ^~~~~~~~~
| std::make_pair
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/ios:40,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_pair.h:567:5: note: ‘std::make_pair’ declared here
567 | make_pair(_T1&& __x, _T2&& __y)
| ^~~~~~~~~
answer.code:43:16: error: ‘q’ was not declared in this scope
43 | while(!q.empty()) {
| ^
answer.code:51:40: error: ‘make_pair’ was not declared in this scope; did you mean ‘std::make_pair’?
51 | q.push(make_pair(-dis[cur->to],cur->to));
| ^~~~~~~~~
| std::make_pair
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/ios:40,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_pair.h:567:5: note: ‘std::make_pair’ declared here
567 | make_pair(_T1&& __x, _T2&& __y)
| ^~~~~~~~~
answer.code: In function ‘void conv()’:
answer.code:62:74: error: ‘min’ was not declared in this scope; did you mean ‘std::min’?
62 | for(j=0;j<k;j++) for(p=k;p>=1;p--) for(i=0;i<(1<<k);i++) f[i][p]=min(f[i][p],f[i^(1<<j)][p-1]);
| ^~~
| std::min
In file included from /usr/include/c++/11/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: ‘std::min’ declared here
3455 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
answer.code:63:56: error: ‘min’ was not declared in this scope; did you mean ‘std::min’?
63 | for(i=0;i<(1<<k);i++) for(p=k;p>=1;p--) dis[i]=min(dis[i],f[i][p]+a[p]);
| ^~~
| std::min
In file included from /usr/include/c++/11/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: ‘std::min’ declared here
3455 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
answer.code: In function ‘void debug()’:
answer.code:66:50: error: ‘cout’ was not declared in this scope; did you mean ‘std::cout’?
66 | for(int i=0;i<(1<<k);i++) if(dis[i]<INF) cout<<dis[i]<<" "; else cout<<"INF ";
| ^~~~
| std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:75,
from answer.code:1:
/usr/include/c++/11/iostream:61:18: note: ‘std::cout’ declared here
61 | extern ostream cout; /// Linked to standard output
| ^~~~
answer.code:66:74: error: ‘cout’ was not declared in this scope; did you mean ‘std::cout’?
66 | for(int i=0;i<(1<<k);i++) if(dis[i]<INF) cout<<dis[i]<<" "; else cout<<"INF ";
| ^~~~
| std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:75,
from answer.code:1:
/usr/include/c++/11/iostream:61:18: note: ‘std::cout’ de...