QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142215 | #1972. JJ Rally | flame | RE | 20ms | 171100kb | C++14 | 2.6kb | 2023-08-18 17:42:15 | 2023-08-18 17:42:17 |
Judging History
answer
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
int const N=1e3,M=1048577,N1=20,M1=30;
int s[2],t[2],dis[M1]; //所有的点需要平移
struct stu1{
int x,y,w;
}ed[N];
struct stu2{
int y,nex,w;
}e[N*2];
long long a[M1],g[2][M],lin[M1],cnt,tot,pw[M],n,m,f[M][N1]; //sosdp一下
int Get(int x,int s1,int t1,int s2,int t2){
if(x==s1) return n;
if(x==t1) return n+1;
if(x==s2) return n-1;
if(x==t2) return n-2;
int y=lower_bound(a,a+cnt,x)-a; //从0开始
if(x!=a[y]) return n+2;
return y;
}
void work(int x,int y,int w){
e[++tot]=(stu2){y,lin[x],w}; lin[x]=tot;
}
bool fl[M1];
#define fi first
#define se second
int lb(int x){
return x&(-x);
}
void sol(int s1,int t1,int s2,int t2,int op){
if(s1==t1) {
g[op][0]=1; return;
}
tot=0;
for(int i=0;i<=n+1;i++) lin[i]=0,dis[i]=1e9,fl[i]=0; //一共是cnt个点
int x,y,w;
for(int i=1;i<=m;i++){
x=ed[i].x; y=ed[i].y; w=ed[i].w;
x=Get(x,s1,t1,s2,t2); y=Get(y,s1,t1,s2,t2);
if(x==n+2||y==n+2) continue;
work(x,y,w); work(y,x,w);
}
dis[n]=0; priority_queue<pair<int,int>> q;
q.push(mp(0,n));
while(q.size()){
x=q.top().se; q.pop();
if(fl[x]) continue;
fl[x]=1;
for(int i=lin[x];i;i=e[i].nex){
y=e[i].y;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push(mp(-dis[y],y));
}
}
}
for(int i=lin[n];i;i=e[i].nex){
y=e[i].y;
if(e[i].w==dis[y]){
if(y==n+1){
g[op][0]++;
//cout<<"qwq"<<endl;
}
else f[1<<y][y]++;
}
}
int w1;
for(int i=1;i<(1<<cnt);i++){
w1=i;
while(w1){
int j=pw[lb(w1)]; w1-=lb(w1);
if(f[i][j]){
for(int k=lin[j];k;k=e[k].nex){
y=e[k].y; w=e[k].w;
if(dis[j]+w==dis[y]){
if(y==n+1) g[op][i]+=f[i][j];
else f[(1<<y)|i][y]+=f[i][j];
}
}
}
}
}
memset(f,0,sizeof(f));
}
void pd(){
if(s[0]==s[1]||t[0]==t[1]||s[0]==t[1]||s[1]==t[0]){
printf("%d",0);
exit(0);
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
ed[i]=(stu1){x,y,w};
} //s=n点 t n+1点 [0,n-1]
scanf("%d%d%d%d",&s[0],&t[0],&s[1],&t[1]);
pd();
for(int i=1;i<=n;i++)
if(i!=s[0]&&i!=s[1]&&i!=t[0]&&i!=t[1]) a[cnt++]=i;
for(int i=0;i<cnt;i++) pw[1<<i]=i;
sol(s[0],t[0],s[1],t[1],0);
// cout<<dis[n]<<' '<<dis[n+1]<<endl;
sol(s[1],t[1],s[0],t[0],1);
int sum=(1<<cnt);
for(int i=0;i<cnt;i++) //sosdp
for(int s=0;s<sum;s++)
if(s&(1<<i)) g[0][s]+=g[0][s^(1<<i)];
long long ans=0; sum--;
// cout<<g[0][0]<<endl;
for(int s=0;s<=sum;s++){
ans+=1ll*g[1][s]*g[0][sum^s];
}
printf("%lld",ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 20ms
memory: 169972kb
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: 16ms
memory: 169472kb
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: 12ms
memory: 171100kb
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
Runtime Error
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 ...