[TIOJ] 1847. 在男子高校尋求邂逅是否搞錯了什麼?

題目連結:http://tioj.infor.org/problems/1847
題目看了一下下才看懂,原來就是給你一張圖問你最短距離小於D的點權和。那要求最短路徑就寫個dijkstra就好,然後再掃一下看某個點距離是不是小於D,是就加點權,不是就不加。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define PB push_back
const int N = 100000 + 5;
const int INF = (1<<30) + 5;

vector<int> G[N];
int dis[N], val[N];
bitset<N> visited;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, d; cin>>n>>m;
	for(int i=0;i<n;i++) cin>>val[i];
	for(int i=0;i<m;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	cin>>d;
	fill(dis, dis+n, INF);
	priority_queue<PII,vector<PII>,greater<PII>> pq;
	dis[0]=0;
	pq.push({dis[0], 0});
	while(!pq.empty()){
		int u = pq.top().SS; pq.pop();
		if(visited[u]) continue;
		visited[u]=1;
		for(auto v:G[u]){
			if(dis[v] > dis[u]+1){
				dis[v]=dis[u]+1;
				pq.push({dis[v], v});
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++) if(dis[i]<=d)
		ans+=val[i];
	cout<<ans<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology