# 牛客国庆集训派对Day3 I Metropolis（多源最短路）

## Metropolis

• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 524288K，其他语言1048576K
• 64bit IO Format: %lld

### 输入

5 6 3
2 4 5
1 2 4
1 3 1
1 4 1
1 5 4
2 3 1
3 4 3

### 输出

3 3 5

### 题意

n个点m条边的无向带权图，求其中p个点每个点到其他p-1个点中最短距离的点的距离（好绕口啊）。

### 题解

• 情况一：$dist(i, j) = min(dist(i, j), dist[u] + dist[v] + w)$
• 情况二：$dist(i, j) = d[i] + w_1 + d[v]$ 、$dist(i, j) = d[j] + w_2 + d[v]$【d[i], d[j]就相当于d[u]】

### 代码

• 286ms 22876KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200010;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int p[maxn], from[maxn]; // from[i]记录点i是由哪个源点扩展的
ll dist[maxn], ans[maxn];
bool vis[maxn];
int n, m, k;

struct Node
{
int v;
ll c;
Node(int _v, ll _c): v(_v), c(_c) {}
bool operator < (const Node & r) const
{
return c > r.c;
}
};

struct Edge
{
int to;
ll w;
Edge(int _to, ll _w): to(_to), w(_w) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, ll w)
{
edge[u].push_back(Edge(v, w));
}

void dijkstra() // 最短路
{
for (int i = 0; i <= n; ++i)
{
vis[i] = false;
dist[i] = inf;
ans[i] = inf;
}
priority_queue <Node> Q;
for (int i = 0; i < k; ++i)
{
dist[p[i]] = 0;
Q.push(Node(p[i], dist[p[i]]));
}
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].to;
ll cost = edge[u][i].w;
if (dist[v] > dist[u] + cost) // 更新最短路
{
dist[v] = dist[u] + cost;
Q.push(Node(v, dist[v]));
from[v] = from[u];
}
else if (from[v] != from[u]) // u和v由不同源点扩展，则更新答案
{
ans[from[u]] = min(ans[from[u]], dist[u] + dist[v] + cost);
ans[from[v]] = min(ans[from[v]], dist[v] + dist[u] + cost);
}
}
}
}

int main()
{
memset(from, 0, sizeof from);
for (int i = 0; i <= n; ++i)
edge[i].clear();
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < k; ++i)
{
scanf("%d", &p[i]);
from[p[i]] = p[i];
}
int u, v;
ll w;
for (int i = 0; i < m; ++i)
{
scanf("%d%d%lld", &u, &v, &w);
}