QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142216#1972. JJ RallyflameWA 13ms168312kbC++142.6kb2023-08-18 17:44:012023-08-18 17:44:05

Judging History

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

  • [2023-08-18 17:44:05]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:168312kb
  • [2023-08-18 17:44:01]
  • 提交

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(y>=cnt) continue;
		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(y>=cnt) continue;
					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: 0
Wrong Answer
time: 13ms
memory: 168312kb

input:

4 4
1 2 2
2 3 1
1 3 1
3 4 1
1 2 3 4

output:

0

result:

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