QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234322#1972. JJ RallyqzzyqWA 102ms12016kbC++142.5kb2023-11-01 15:56:572023-11-01 15:56:57

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 15:56:57]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:12016kb
  • [2023-11-01 15:56:57]
  • 提交

answer

#include<bits/stdc++.h>
#define int 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: 5852kb

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: 3824kb

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: 3836kb

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: 102ms
memory: 12016kb

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'