QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234310 | #1972. JJ Rally | qzzyq | WA | 96ms | 13564kb | C++14 | 2.1kb | 2023-11-01 15:47:10 | 2023-11-01 15:47:10 |
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];
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'