求条
查看原帖
求条
751062
Diary_Of_Young楼主2024/12/9 15:27
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2e7 + 10;
#define int long long
int n , m , q;
int e[M] , h[M] , ne[M] , w[M] , idx = 0;
void init()
{
	memset(h , -1 , sizeof h);
	idx = 0;
}


int dist[N] , v[N];

void add(int x , int y , int k)
{
	w[++ idx] = k , e[idx] = y , ne[idx] = h[x] , h[x] = idx;
}

pair<int , int> spfa(int x)
{
	queue<int> q;
	memset(dist , 0x3f , sizeof dist);
	memset(v , 0 , sizeof v);
	dist[x] = 0 , v[x] = 1;
	q.push(x);
	while(!q.empty())
	{
		int u = q.front() ; q.pop();
		v[u] = 0;
		for(int i = h[u] ; ~i ; i = ne[i])
		{
			int y = e[i] , z = w[i];
			if(dist[y] > dist[u] + z)
			{
				dist[y] = dist[u] + z;
				if(!v[y]) v[y] = 1 , q.push(y);
			}
		//	cout << 1;
		}
		
	}
	int res = -1 , cnt = 0;
	for(int i = 0 ; i <= n ; i ++)
		if(dist[i] < 0x3f - 10)
			res = max(res , dist[i]) ;// cout << dist[i] << endl;
	for(int i = 0 ; i <= n ;i ++)
		cnt += (dist[i] == res);
	return make_pair(res , cnt);
}

signed main()
{
	init();
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1 ; i <= m ; i ++) 
	{
		int a , b , w;
		cin >> a >> b>> w;
		if(a != b)
		{
			add(a , b , w);
			add(b , a , w); 
		}
	}
	while(q --)
	{
		int s;
		cin >> s;
		pair<int , int> ans = spfa(s);
		cout << ans.first << ' ' << ans.second << endl;
	}
	cout << endl;
	return 0;
}
2024/12/9 15:27
加载中...