20pts求掉
查看原帖
20pts求掉
1449703
Ak_hjc_using楼主2024/12/2 21:23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e3 + 5;
int n, m, s, t, k, g, T[N], u[N], v[N], w[N], dis[N];
bool vis[N];
int a[N][N];

struct Tman
{
	int lt;
	int rt;	
}Tman[N][N];

struct Node
{
	int id, w;
	bool operator < (const Node &a) const
	{
		return w > a.w;
	}
};

struct Edge 
{
	int v, w;
};

vector<Edge> G[N];

void Spfa(int s)
{
	for (int i = 1;i <= n;i ++)
	{
		dis[i] = 0x3f3f3f3f;
		vis[i] = false;
	}	
	queue<int> q;
	dis[s] = k;
	vis[s] = true;
	q.push(s);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int i = 0;i < G[u].size();i ++)
		{
			Edge t = G[u][i];
			int num = 0;
			if (dis[u] >= Tman[u][t.v].lt && dis[u] <= Tman[u][t.v].rt)
			{
				num = Tman[u][t.v].rt - dis[u];
			}
			if (dis[t.v] > dis[u] + t.w + num)
			{
				dis[t.v] = dis[u] + t.w + num;
				if (vis[t.v] == false)
				{
					vis[t.v] = true;
					q.push(t.v);
				}
			}
		}
	}
	return ;
}

void add_edge(int u, int v, int w)
{
	G[u].push_back({v, w});
	G[v].push_back({u, w});
	return ;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> s >> t >> k >> g;
	for (int i = 1;i <= g;i ++) cin >> T[i];
	for (int i = 1;i <= m;i ++)
	{
		cin >> u[i] >> v[i] >> w[i];
		add_edge(u[i], v[i], w[i]);
		a[u[i]][v[i]] = w[i];
		a[v[i]][u[i]] = w[i];
	}
	int Time = 1;
	for (int i = 2;i <= g;i ++)
	{
		Tman[T[i - 1]][T[i]].rt = Time + a[T[i - 1]][T[i]] - 1;
		Tman[T[i - 1]][T[i]].lt = Time;
		Tman[T[i]][T[i - 1]].rt = Time + a[T[i - 1]][T[i]] - 1;
		Tman[T[i]][T[i - 1]].lt = Time;
		Time = Time + a[T[i - 1]][T[i]];
	}
	Spfa(s); 
	cout << dis[t] - k << endl;
	return 0;
}

2024/12/2 21:23
加载中...