QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#324913	#8232. Yet Another Shortest Path Query	ucup-team197^#	WA	428ms	136644kb	C++14	2.3kb	2024-02-11 01:32:15	2024-02-11 01:32:15

Judging History

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

[2024-02-11 01:32:15]
评测

测评结果：WA
用时：428ms
内存：136644kb

查看

[2024-02-11 01:32:15]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int iu=19;
#define fi first
#define se second
int n,m,q;
vector<pair<ll,int> >adj[N],out[N],in[N];
int deg[N];
int ord[N];
vector<pair<int,int> >qry[N];
ll ans[N];

int qid[N];
ll best[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m ;i++){
		int u,v,w;cin >> u >> v >> w;
		adj[u].push_back({w,v});
		adj[v].push_back({w,u});
		deg[u]++;deg[v]++;
	}
	stack<int>s;
	for(int i=1; i<=n ;i++){
		if(deg[i]<=5) s.push(i);
	}
	for(int i=1; i<=n ;i++){
		int x=s.top();s.pop();
		ord[x]=i;
		for(auto c:adj[x]){
			if(ord[c.se]) continue;
			in[c.se].push_back({c.fi,x});
			out[x].push_back(c);
			if(--deg[c.se]==5){
				s.push(c.se);
			}
		}
	}
	cin >> q;
	for(int i=1; i<=q ;i++){
		int u,v;cin >> u >> v;
		qry[u].push_back({i,v});
		qry[v].push_back({i,u});
		ans[i]=1e18;
		{
			for(auto c:out[u]){
				if(c.se==v) ans[i]=min(ans[i],c.fi);
				for(auto d:out[c.se]){
					if(d.se==v) ans[i]=min(ans[i],c.fi+d.fi);
					for(auto e:out[d.se]){
						if(e.se==v) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
					}
					for(auto e:out[v]){
						if(e.se==d.se) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
					}
				}
			}
			
		}
		swap(u,v);
		{
			for(auto c:out[u]){
				if(c.se==v) ans[i]=min(ans[i],c.fi);
				for(auto d:out[c.se]){
					if(d.se==v) ans[i]=min(ans[i],c.fi+d.fi);
					for(auto e:out[d.se]){
						if(e.se==v) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
					}
					for(auto e:out[v]){
						if(e.se==d.se) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
					}
				}
			}
			
		}
	}
	for(int i=1; i<=n ;i++) best[i]=1e18,qid[i]=0;
	for(int t=1; t<=n ;t++){
		for(auto c:qry[t]) qid[c.se]=c.fi;
		for(auto c:in[t]){
			for(auto d:out[c.se]){
				best[d.se]=min(best[d.se],c.fi+d.fi);
				if(qid[d.se]) ans[qid[d.se]]=min(ans[qid[d.se]],best[d.se]);
				for(auto e:out[d.se]){
					if(qid[e.se]) ans[qid[e.se]]=min(ans[qid[e.se]],best[d.se]+e.fi);
				}
			}
		}
		for(auto c:qry[t]){
			for(auto d:out[c.se]){
				ans[c.fi]=min(ans[c.fi],d.fi+best[d.se]);
			}
		}
		for(auto c:in[t]){
			for(auto d:out[c.se]){
				best[d.se]=1e18;
			}
		}
		for(auto c:qry[t]) qid[c.se]=0;
	}
	for(int i=1; i<=q ;i++){
		if(ans[i]==1e18) cout << "-1\n";
		else cout << ans[i] << '\n';
	}
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 11ms

memory: 97520kb

input:

output:

result:

ok 5 number(s): "6 8 3 1 7"

Test #2:

score: 0

Accepted

time: 15ms

memory: 97388kb

input:

output:

3
-1
-1

result:

ok 3 number(s): "3 -1 -1"

Test #3:

score: -100

Wrong Answer

time: 428ms

memory: 136644kb

input:

40005 79608
1 2 70031203
1 3 99924845
1 4 61645659
1 5 9324967
2 3 15761918
3 4 62534796
4 5 35260314
5 2 35948540
6 2 23727405
6 7 83302920
7 3 31010426
7 8 75060393
8 4 94275932
8 9 99663793
9 5 81701979
9 6 439297
10 6 46955645
10 11 89514237
11 7 21257310
11 12 53896253
12 8 67933315
12 13 26161...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 10014th numbers differ - expected: '149846554', found: '155353090'