WA80玄关
  • 板块P4943 密室
  • 楼主ChampionCyan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/9 18:04
  • 上次更新2024/5/9 18:08:24
查看原帖
WA80玄关
1036180
ChampionCyan楼主2024/5/9 18:04
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int n, m, k, ans, dis1[MAXN], dis2[MAXN];
bool go[MAXN], vis[MAXN];

struct edge {
	int v, w;
};

vector <edge> e[MAXN];

struct node {
	int u, dis;
	bool operator > (const node& a) const {
		return dis > a.dis;
	}
} ;

void dijkstra1(int begin) {
	for (int i = 1; i <= n; i++)
		dis1[i] = 1e9, vis[i] = false;
	priority_queue < node, vector < node >, greater < node > > q;
	q.push({begin, 0});
    dis1[1] = 0;
	while (!q.empty()) {
		int u = q.top().u;
        q.pop();
		if (vis[u])
            continue;
        vis[u] = true;
		for (edge ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis1[v] > dis1[u] + w) {
                dis1[v] = dis1[u] + w;
                q.push({v, dis1[v]});
            }
        }
	}
}

void dijkstra2(int begin) {
	for (int i = 1; i <= n; i++)
		dis2[i] = 1e9, vis[i] = false;
	priority_queue < node, vector < node >, greater < node > > q;
	q.push({begin, 0});
    dis2[1] = 0;
	while (!q.empty()) {
		int u = q.top().u;
        q.pop();
		if (vis[u])
            continue;
        vis[u] = true;
		for (edge ed : e[u]) {
            int v = ed.v;
            int w = ed.w;
            if (dis2[v] > dis2[u] + w && !go[v]) {
                dis2[v] = dis2[u] + w;
                q.push({v, dis2[v]});
            }
        }
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (k--) {
		int snake;
		scanf("%d", &snake);
		go[snake] = true;
	}
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		e[a].push_back({ b, c }), e[b].push_back({ a, c });
	}
	int x, y;
	scanf("%d%d", &x, &y);
	dijkstra1(1);
    dijkstra2(1);
    int sum1 = dis1[x], sum2 = dis1[y], sum3 = dis2[x], sum4 = dis2[y];
    ans = min(max(sum1, sum4), max(sum2, sum3));
    dijkstra1(x);
    ans = min(ans, sum1 + dis1[y]);
    dijkstra1(y);
    ans = min(ans, sum2 + dis1[x]);
	printf("%d", ans);
	return 0;
}
2024/5/9 18:04
加载中...