c++邮递员投递经过特定点_luoguP1629 邮递员送信

建一个正向图和反向图，(都存到一个地方，反向图的节点加 n 就好了)，跑两边 Dijskra

#include

using namespace std;

const int N = 1e3 + 10,M = 1e5 + 10,INF = 0x3f3f3f3f;

typedef pair PII;

typedef long long LL;

int e[M*2],ne[M*2],w[M*2],h[N*2],idx,n,m;

LL dist[N*2];

bool st[N*2];

void add(int a,int b,int c) {

e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;

}

void dij(int s) {

for(int i = 1;i <= n * 2; ++i) dist[i] = INF;

dist[s] = 0;

priority_queue,greater > q;

q.push(make_pair(0,s));

while(q.size()) {

auto ver = q.top().second;

q.pop();

if(st[ver]) continue;

st[ver] = 1;

for(int i = h[ver]; ~i;i = ne[i]) {

int j = e[i];

if(dist[j] > dist[ver] + w[i]) {

dist[j] = dist[ver] + w[i];

q.push(make_pair(dist[j],j));

}

}

}

}

int main() {

memset(h,-1,sizeof h);

cin >> n >> m;

for(int i = 0;i < m; ++i) {

int a,b,c;

cin >> a >> b >> c;

add(a,b,c);// 正向边

add(b + n,a + n,c);// 反向边

}

LL sum = 0;

dij(1);

for(int i = 2;i <= n; ++i) sum += dist[i];

dij(1 + n);

for(int i = 2 + n;i <= n * 2; ++i) sum += dist[i];

cout << sum << endl;

return 0;

}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！