#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5, mod = 1e9+7;
int a[N], n, m;
int d[N];
bool vis[N];
int num, wt, bt, v;
struct node {
	int y, w;
	bool operator < (const node a) const {
		return w > a.w;
	}
};
vector<node> g[N];
int f[N];
void dijkstra(int s) {
	memset(d, 0x3f, sizeof d);
	memset(f, 0x3f, sizeof f);
	priority_queue<node> q;
	d[s] = 0;
	f[s] = 0;
	q.push({s, 0});
	while(!q.empty()) {
		node t = q.top();
		int x = t.y;
		q.pop();
		if(vis[x]) continue;
		vis[x] = true;

		for(int i = 0; i < g[x].size(); i++) {
			int y = g[x][i].y, w = g[x][i].w;
			if(vis[y]) continue;
			if(d[y] > d[x] + w) {
				d[y] = d[x] + w;
				f[y] = f[x];
				if(y > n && x > n){
					f[y] += v;
				}
				q.push({y, d[y]});
			} else if(d[y] == d[x] + w){
				if(y <= n || x <= n) {
					f[y] = min(f[y], f[x]);
				} else {
					f[y] = min(f[y], f[x] + v);
				}
			}
		}
	}
}

signed main() {
	
	cin >> n >> m >> num >> wt >> bt >> v;
	for(int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		g[x].push_back({x+n, 0});
		g[x+n].push_back({x, 0});
	}
	for(int i = 1; i <= num; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back({y, wt});
		g[y].push_back({x, wt});
		g[x+n].push_back({y+n, bt});
		g[y+n].push_back({x+n, bt});
	}
	int s, e;
	cin >> s >> e;
	dijkstra(s);
	cout << d[e] << " " << f[e];
	return 0;
}


0 条评论

目前还没有评论...

信息

ID
496
时间
ms
内存
MiB
难度
5
标签
递交数
57
已通过
21
上传者