时间限制: 1 Sec 内存限制: 128 MB 题目描述
小L的家乡最近遭遇了一场洪水，城市变得面目全非，道路也都被冲毁了。生活还要继续，于是市政府决定重建城市中的道路。
在洪水到来前，城市中共有n个区域和m条连接这些区域的双向道路， 道路连通了所有的区域，为了方便人们的出行，只能重建这些原有的道路，
不能建新的道路。编号为s的区域是市政广场，市政府希望重建的道路能够 使得所有区域到市政广场的最短路与受灾前保持不变，同时为了节约救灾
经费，还要使得修建的所有道路的长度和尽可能小。 小L为了拯救心爱的家乡，决定站出来，成为优秀的青年理论计算机科
学家，于是马上投入到了对这个问题的研究中。你能帮帮小L吗？输入
第一行两个整数n和m，表示区域与道路的个数。
接下来m行，每行三个正整数u，v和w，描述一条连接u和v、长为w的道路。 最后一行，一个正整数s，表示市政广场的编号。输出
输出一个整数，表示最小长度和。 样例输入 5 7 1 2 1 2 3 4 2 4 2 4 3 2 5 2 2 4 5 1 5 1 1
2 样例输出 6 提示 最优方案是重建1-2,1-5,2-4,4-3的道路，此时所有区域到达区域2的最短路分别是1, 0, 4, 2,
2，道路长度和是1 + 1 + 2 + 2 = 6。 对于20%的数据，n ≤ 10, m ≤ 20； 对于另外30%的数据，边权不超过2；
对于100%的数据，1 ≤ n ≤ 105, n − 1 ≤ m ≤ 2 ∗ 105, 1 ≤ w ≤ 109。来源 2018山东冬令营
先跑一遍Dijkstra，求出原点到每个点的最短路径长度d[i]，
再一模一样跑一遍Dijkstra,只不过在每次更新操作时，维护每个点的最小入度值。
具体就是 如果dd[u]（当前求得的原点到u的最短路长度）+e(u,v).w == d[v]（第一次求得的最短路），
就维护d2[v] = min(d2[v],e(u,v).w);
#define FILE() freopen("../../in.txt","r",stdin)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//const int MOD = 1e9+7;
const int maxn = 100005,maxm = 200005;
const ll INF = 1e16+5;
int n,m,head[maxn],cnt;
ll d[maxn],dd[maxn],d2[maxn];
struct edge {
int v,nex;
ll w;
} ed[maxm*2];
struct node1{
int num,len;
};
struct node2{
int num,len;
};
bool operator < (node1 a,node1 b){
return d[a.num]>d[b.num];
}
bool operator < (node2 a,node2 b){
return dd[a.num]>dd[b.num];
}
priority_queue <node1> q;
priority_queue <node2> qq;
void addedge(int _u,int _v,ll _w) {
cnt++;
ed[cnt].v = _v;
ed[cnt].w = _w;
ed[cnt].nex = head[_u];
head[_u] = cnt;
}
void dij1(int start) {
for(int i=1;i<=n;i++)d[i] = INF;
d[start] = 0;
while(!q.empty())q.pop();
q.push((node1){start,0});
while(!q.empty()) {
int cur = q.top().num,len = q.top().len;
q.pop();
if(d[cur]<len)continue;
for(int i=head[cur]; i; i=ed[i].nex) {
int v=ed[i].v;
if(d[v]>d[cur]+ed[i].w){
d[v] = d[cur]+ed[i].w;
q.push((node1){v,d[v]});
}
}
}
}
void dij2(int start){
for(int i=1;i<=n;i++)dd[i] = d2[i] = INF;
dd[start] = d2[start] = 0;
while(!qq.empty())qq.pop();
qq.push((node2){start,0});
while(!qq.empty()) {
int cur = qq.top().num,len = qq.top().len;
qq.pop();
if(dd[cur]<len)continue;
for(int i = head[cur];i;i=ed[i].nex){
int v=ed[i].v;
if(dd[v]>dd[cur]+ed[i].w){
dd[v] = dd[cur]+ed[i].w;
qq.push((node2){v,dd[v]});
}
if(d[v]==dd[cur]+ed[i].w){
d2[v] = min(d2[v],ed[i].w);
}
}
}
}
int main() {
// FILE();
// freopen("../../out.txt","w",stdout);
cin>>n>>m;
for(int i=0; i<m; i++) {
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
int s;
cin>>s;
dij1(s);
dij2(s);
ll sum = 0;
for(int i=1;i<=n;i++)sum+=d2[i];
cout<<sum<<endl;
return 0;
}