LOJ#3087. 「GXOI / GZOI2019」旅行者

正着求一遍dij，反着求一遍，然后枚举每条边，从u到v，如果到u最近的点和v能到的最近的点不同，那么可以更新答案

没了

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

    int64 val;

}E[500005];

int N,M,K;

int head[MAXN],sumE,u[500005],v[500005],c[500005];

vector<int> st;

int64 dis[2][MAXN],from[2][MAXN];

bool vis[MAXN];

void add(int u,int v,int64 c) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    E[sumE].val = c;

    head[u] = sumE;

}

void Init() {

    read(N);read(M);read(K);

    int a,b;

    for(int i = 1 ; i <= M ; ++i) {

	read(u[i]);read(v[i]);read(c[i]);

    }

    st.clear();

    for(int i = 1 ; i <= K ; ++i) {

	read(a);st.pb(a);

    }

}

priority_queue<pair<int64,int> > Q;

void Dijkstra(int id) {

    for(int i = 1 ; i <= N ; ++i) {

	dis[id][i] = 1e18;

    }

    for(auto t : st) {

	dis[id][t] = 0;from[id][t] = t;

	Q.push(mp(-dis[id][t],t));

    }

    memset(vis,0,sizeof(vis));

    while(!Q.empty()) {

	auto now = Q.top();Q.pop();

	if(vis[now.se]) continue;

	int t = now.se;

	vis[t] = 1;

	for(int i = head[t] ; i ; i = E[i].next) {

	    int v = E[i].to;

	    if(dis[id][v] > dis[id][t] + E[i].val) {

		dis[id][v] = dis[id][t] + E[i].val;

		from[id][v] = from[id][t];

		Q.push(mp(-dis[id][v],v));

	    }

	}

    }

}

void Solve() {

    sumE = 0;memset(head,0,sizeof(head));

    for(int i = 1 ; i <= M ; ++i) {

	add(u[i],v[i],c[i]);

    }

    Dijkstra(0);

    sumE = 0;memset(head,0,sizeof(head));

    for(int i = 1 ; i <= M ; ++i) {

	add(v[i],u[i],c[i]);

    }

    Dijkstra(1);

    int64 ans = 1e18;

    for(int i = 1 ; i <= M ; ++i) {

	if(from[0][u[i]] != from[1][v[i]]) {

	    ans = min(ans,c[i] + dis[0][u[i]] + dis[1][v[i]]);

	}

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    int T;

    read(T);

    while(T--) {

	Init();

	Solve();

    }

}

巴特西

【LOJ】#3087. 「GXOI / GZOI2019」旅行者

LOJ#3087. 「GXOI / GZOI2019」旅行者

最新文章

热门文章