QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#247500#6523. Escape PlangzzzWA 0ms5924kbC++201.4kb2023-11-11 14:39:492023-11-11 14:39:50

Judging History

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

  • [2023-11-11 14:39:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5924kb
  • [2023-11-11 14:39:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<pair<int,ll>> e[maxn];
ll num[maxn],dis[maxn],n,m,k;;
bool ex[maxn],vis[maxn];
struct node{
	int fr;
	ll w;
	friend bool operator <(node x,node y){ 	
		return x.w>y.w;
	}
};
void dij(){
	priority_queue<node,vector<node>> sq;
	for(int i=1;i<=n;i++){
		if(ex[i]) {
			dis[i]=0;
			sq.push((node){i,dis[i]});
		}
	}
	while(!sq.empty()){
		int now=sq.top().fr;
		sq.pop();
		if(num[now]) {
			num[now]--;
			continue;
		}
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=0;i<e[now].size();i++){
			int to=e[now][i].first,w=e[now][i].second;
			if(dis[to]>dis[now]+w){
				dis[to]=dis[now]+w;
				sq.push((node){to,dis[to]});
			}
		}
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;cin>>t;
	while(t--) {
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++){
			e[i].clear();
			dis[i]=1e18;
			num[i]=0;
			ex[i]=false;
			vis[i]=false;
		}
		for(int i=1;i<=k;i++) {
			int x;cin>>x;
			ex[x]=true;
		}
		for(int i=1;i<=n;i++){
			cin>>num[i];
		}
		for(int i=1;i<=m;i++){
			int fr,to,w;
			cin>>fr>>to>>w;
			e[fr].push_back(pair<int,ll>(to,w));
			e[to].push_back(pair<int,ll>(fr,w));
		}
		dij();
		if(dis[1]==1e18) cout<<"-1\n";
		else cout<<dis[1]<<"\n";
	}
}
/*
  2
  3 4 1
  3
  1 1 1
  1 2 1
  1 2 2
  2 3 1
  2 3 2
  3 2 2
  2 3
  2 0 0
  1 2 1
  1 3 1

 */

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5924kb

input:

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

output:

-1
1

result:

wrong answer 1st numbers differ - expected: '4', found: '-1'