今晚E题求条
  • 板块学术版
  • 楼主Ekin123
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/7/26 21:43
  • 上次更新2025/7/27 08:55:13
查看原帖
今晚E题求条
1235038
Ekin123楼主2025/7/26 21:43
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

int n,m;
int k,t;

struct edge
{
	long long v,w;
};

vector<edge> e[505];

long long dis[505];

bool vis[505];

void dijkstra(int s)
{
	priority_queue<pair<long long,int>,
	vector<pair<long long,int> >,
	greater<pair<long long,int> > > q;
	for(int i = 0;i <= n;i++)
	{
		dis[i] = 1e18;
		vis[i] = 0;
	}
	dis[s] = 0;
	q.push({0,s});
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto ed : e[u])
		{
			int v = ed.v;
			long long w = ed.w;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push({dis[v],v});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	while(m--)
	{
		int a,b,c;
		cin >> a >> b >> c;
		e[a].push_back({b,c});
		e[b].push_back({a,c});
	}
	cin >> k >> t;
	while(k--)
	{
		int a;
		cin >> a;
		e[a].push_back({0,t});
		e[0].push_back({a,0});
	}
	int q;
	cin >> q;
	while(q--)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int x,y,t;
			cin >> x >> y >> t;
			e[x].push_back({y,t});
			e[y].push_back({x,t});
		}
		else if(op == 2)
		{
			int x;
			cin >> x;
			e[x].push_back({0,t});
			e[0].push_back({x,0});
		}
		else
		{
			long long ans = 0;
			for(int i = 1;i <= n;i++)
			{
				dijkstra(i);
				for(int j = 1;j <= n;j++)
				{
					ans += (dis[i] == 1e18 ? 
					0 : dis[i]); 
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
} 
2025/7/26 21:43
加载中...