Bear and Clique Distances（构造基点+Dijkstra）
Bearland consists of N cities, numbered 1 through N. Cities are connected with bidirectional roads.
Cities 1 through K were built a long time ago, when citizens liked order and regularity. Each pair of those old cities is connected with a road of length X. Note that this description generates K*(K-1)/2 roads.
There are M newer roads, not necessarily of the same lengths. The i-th of them connects cities ai and bi and has length ci.
There is no road that connects a city to itself. All M+K*(K-1)/2 roads are distinct (ie. no two of them connects the same pair of cities). It's guaranteed that it's possible to get from every city to every other city, using one or more roads.
Limak, a bear, lives in the city S. In order to plan a trip to some other city, for every city he wants to know how quickly he can get there. Can you help him and find the distance from S to every city?
The distance between two cities is the minimum total length of a path (sequence of roads) between the two cities.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains five integers N, K, X, M and S, denoting the number of cities, the number of old cities, the length of a road between every two old cities, the number of newer roads, and the city where Limak lives, respectively.
Each of the following M lines contains three integers ai, bi and ci, denoting a road of length ci between cities ai and bi.
As guaranteed above: no two cities are connected with more than one road, no road connects a city to itself, and it's possible to get from every city to every other city.
Constraints
- 1 ≤ T ≤ 3
- 2 ≤ K ≤ N ≤ 105
- 0 ≤ M ≤ 105
- 1 ≤ S, ai, bi ≤ N
- 1 ≤ X, ci ≤ 109
Output
For each test case, output a single line containing N integers. The i-th of them should denote the distance from the city S to the city i. The distance from S to Sis simply 0.
Sample Input
3 5 4 100 2 3 1 5 50 5 3 160 5 4 100 2 3 1 5 50 5 3 140 8 3 15 7 5 3 4 10 4 5 20 5 6 10 6 1 7 3 7 1000 7 8 50 3 5 1000000000
Sample Output
100 100 0 100 150 100 100 0 100 140 17 32 30 20 0 10 1030 1080
Hint
Test case 1. There are N = 5 cities. The first K = 4 of them are all connected with each other with roads of length X = 100. There are M = 2 extra roads:
- Cities 1 and 5 are connected with a road of length 50.
- Cities 5 and 3 are connected with a road of length 160.
We are asked to compute distances to all cities from the city S = 3. Note that the distance from a city to itself is 0, and this is why the third number in the ouput is 0.
输入的第一行包含一个整数T，代表测试数据的组数。接下来是T组数据。
每组数据的第一行包含五个整数N、K、X、M和S，分别代表城市数、古城数、古城间的道路长度、新建道路的条数，以及Limak居住在的城市编号。接下来M行，每行包含三个整数ai、bi和ci，代表有一条连接编号为ai和bi的城市的长度为ci的新建道路。保证不存在由一个城市连向自己的道路，所有道路两两不同，且任意城市间两两可达。编号为1-K的城市都是古城，那里的市民们喜欢秩序与规律。这些城市两两由长度为X的双向道路连接，共有K(K - 1) / 2条这样的道路
我们可以拿出一点来当做一个基站来访问其他的节点。这个节点到其他1-k个节点的权值都是x，而1-k个节点到这个基站的权值是0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=1000000000000000LL;
struct node{
int v;
ll c;
node(){}
node(int vv,ll cc){
v=vv;
c=cc;
}
};
struct Node{
int u;
ll c;
Node(){}
Node(int uu,ll cc){
u=uu;
c=cc;
}
bool operator<(const Node other)const{
return c>other.c;
}
};
vector<node> G[N];
ll dis[N];
bool vis[N];
void dijkstra(int n,int s){
priority_queue<Node> q;
for(int i=0;i<=n;i++){
dis[i]=INF;
vis[i]=0;
}
dis[s]=0;
q.push(Node(s,0));
while(!q.empty()){
Node temp=q.top();
q.pop();
int u=temp.u;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<G[u].size();i++){
node tmp=G[u][i];
int v=tmp.v;
ll c=tmp.c;
if(dis[v]>dis[u]+c){
dis[v]=dis[u]+c;
q.push(Node(v,dis[v]));
}
}
}
for(int i=1;i<=n;i++){
printf("%lld%c",dis[i]," \n"[i==n]);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k,m,s;
ll x;
scanf("%d%d%lld%d%d",&n,&k,&x,&m,&s);
for(int i=0;i<=n;i++) G[i].clear();
while(m--){
int u,v;
ll c;
scanf("%d%d%lld",&u,&v,&c);
G[u].push_back(node(v,c));
G[v].push_back(node(u,c));
}
for(int i=1;i<=k;i++){
G[0].push_back(node(i,x));
G[i].push_back(node(0,0LL));
}
dijkstra(n,s);
}
return 0;
}
字节跳动公司氛围 553人发布