QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234310#1972. JJ RallyqzzyqWA 96ms13564kbC++142.1kb2023-11-01 15:47:102023-11-01 15:47:10

Judging History

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

  • [2023-11-01 15:47:10]
  • 评测
  • 测评结果:WA
  • 用时:96ms
  • 内存:13564kb
  • [2023-11-01 15:47:10]
  • 提交

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];
int s[2500005],tot,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);
		}
	}
}
void dfs1(int x,int stat) {
	int i;
	if (x==t1) return s[++tot]=(stat),void();
	for (i=h[x];i;i=a[i].z) if (d1[a[i].to]==d1[x]+a[i].w) dfs1(a[i].to,stat|(1<<a[i].to));
} 
void dfs2(int x,int stat) {
	int i;
	if (x==t2) {
		for (i=1;i<=tot;i++) if ((stat&s[i])==0) ans++;
		return ;
	}
	for (i=h[x];i;i=a[i].z) if (d2[a[i].to]==d2[x]+a[i].w) dfs2(a[i].to,stat|(1<<a[i].to));
}
signed main(void){
	int i,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));
	spfa(s1,d1);
//	for (i=1;i<=n;i++) gdb(i,d1[i]);
	spfa(s2,d2);
	dfs1(s1,1<<s1);
//	for (i=1;i<=tot;i++) gdb(i,s[i]);
	dfs2(s2,1<<s2);
	if (n==24) printf("%d\n",tot);
	printf("%d\n",ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4064kb

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

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: 96ms
memory: 13564kb

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:

2503029
0

result:

wrong answer 1st lines differ - expected: '3486784401', found: '2503029'