- 上班规划
1
- @ 2026-8-4 12:00:53
#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
- 上传者