QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234321 | #1972. JJ Rally | qzzyq | WA | 104ms | 7960kb | C++14 | 2.5kb | 2023-11-01 15:56:32 | 2023-11-01 15:56:32 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 3005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,m;
int ans;
int h[maxn],head=1;
struct yyy {
int to,z,w;
void add(int x,int y,int val) {
to=y;z=h[x];h[x]=head;w=val;
}
}a[maxn];
int d1[maxn],d2[maxn],N;
int s1,t1,s2,t2;
void spfa(int s,int *dis) {
int i;
queue<int>q;
q.push(s);dis[s]=0;
while (!q.empty()) {
int x=q.front();q.pop();
for (i=h[x];i;i=a[i].z) if (dis[a[i].to]>dis[x]+a[i].w) {
dis[a[i].to]=dis[x]+a[i].w;
q.push(a[i].to);
}
}
}
int vis[maxn],f[(1<<20)+5],id[maxn],tot;
void dfs1(int x,int stat) {
int i;
if (x==t1) return ++tot,f[stat]++,void();
for (i=h[x];i;i=a[i].z)
if (d1[a[i].to]==d1[x]+a[i].w&&vis[a[i].to]!=2) {
if (!vis[a[i].to]) dfs1(a[i].to,stat|(1<<id[a[i].to]));
else dfs1(a[i].to,stat);
}
}
void dfs2(int x,int stat) {
int i;
if (x==t2) {
ans+=f[(N-1)^stat];
// gdb(stat,f[(N-1)^stat],ans);
return ;
}
for (i=h[x];i;i=a[i].z)
if (d2[a[i].to]==d2[x]+a[i].w&&vis[a[i].to]!=1) {
if (!vis[a[i].to]) dfs2(a[i].to,stat|(1<<id[a[i].to]));
else dfs2(a[i].to,stat);
}
}
signed main(void){
int i,j,x,y,z;
read(n);read(m);
for (i=1;i<=m;i++) {
read(x),read(y);read(z);
a[++head].add(x,y,z);
a[++head].add(y,x,z);
}
read(s1),read(t1),read(s2),read(t2);
memset(d1,0x3f,sizeof(d1));
memset(d2,0x3f,sizeof(d2));
vis[s1]=vis[t1]=1;vis[s2]=vis[t2]=2;
spfa(s1,d1);
spfa(s2,d2);
int times=0;
for (i=1;i<=n;i++) if (vis[i]==0) id[i]=times++;
dfs1(s1,0);
N=(1<<n-4);
// for (i=0;i<N;i++) gdb(i,f[i]);
for (j=0;j<n-4;j++) {
for (i=0;i<N;i++) if ((i>>j)&1) {
f[i]+=f[i^(1<<j)];
}
}
// for (i=0;i<N;i++) gdb(i,f[i]);
dfs2(s2,0);
// if (n==24) printf("%d\n",tot);
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5932kb
input:
4 4 1 2 2 2 3 1 1 3 1 3 4 1 1 2 3 4
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
4 3 1 2 1 2 3 1 3 4 1 1 3 2 4
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
6 8 1 4 1 1 3 1 4 2 1 3 2 1 1 2 2 1 5 1 5 2 1 5 6 2 1 2 6 5
output:
3
result:
ok single line: '3'
Test #4:
score: -100
Wrong Answer
time: 104ms
memory: 7960kb
input:
24 276 1 2 117 1 3 36 1 4 247 1 5 150 1 6 215 1 7 232 1 8 161 1 9 209 1 10 190 1 11 4 1 12 102 1 13 281 1 14 301 1 15 32 1 16 138 1 17 114 1 18 304 1 19 141 1 20 105 1 21 64 1 22 75 1 23 23 1 24 237 2 3 153 2 4 364 2 5 267 2 6 332 2 7 349 2 8 278 2 9 326 2 10 307 2 11 113 2 12 219 2 13 398 2 14 418 ...
output:
-808182895
result:
wrong answer 1st lines differ - expected: '3486784401', found: '-808182895'