题解 P1629 【邮递员送信】
Ryan_
2019-10-04 20:10:39
水一篇题解
很经典的思路：
求其他点到源点的距离，反向建边，再从源点跑一边最短路
80分做法：
```
#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int n,m,st,ed,nxt[N],first[N],go[N],w[N],tot,dd[N];
int d[N];
bool v[N];
priority_queue<pair<int ,int > >q;
inline void add(int x,int y,int z)
{
nxt[++tot]=first[x];first[x]=tot;go[tot]=y;w[tot]=z;
}
void dijkstra(int x){
memset(d,0x3f,sizeof d);
memset(v,0,sizeof v);
d[x]=0;
q.push(make_pair(0,x));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
for(int i=first[x];i;i=nxt[i]){
int y=go[i],z=w[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
void dijkstra1(int x){
memset(dd,0x3f,sizeof dd);
memset(v,0,sizeof v);
dd[x]=0;
q.push(make_pair(0,x));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
for(int i=first[x];i;i=nxt[i]){
int y=go[i],z=w[i];
if(dd[y]>dd[x]+z){
dd[y]=dd[x]+z;
q.push(make_pair(-dd[y],y));
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
long long ans=0;
dijkstra1(1);
for(int i=1;i<=n;i++){
ans+=dd[i];
dijkstra(i);
ans+=d[1];
}
printf("%lld",ans);
return 0;
}
```
100做法：
```
#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int n,m,st,ed,nxt[N],first[N],go[N],w[N],tot,dd[N];
int d[N];
bool v[N];
priority_queue<pair<int ,int > >q;
struct node{
int a,b,c;
}e[N];
inline void add(int x,int y,int z)
{
nxt[++tot]=first[x];first[x]=tot;go[tot]=y;w[tot]=z;
}
void dijkstra(int x){
memset(d,0x3f,sizeof d);
memset(v,0,sizeof v);
d[x]=0;
q.push(make_pair(0,x));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
for(int i=first[x];i;i=nxt[i]){
int y=go[i],z=w[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
void dijkstra1(int x){
memset(dd,0x3f,sizeof dd);
memset(v,0,sizeof v);
dd[x]=0;
q.push(make_pair(0,x));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
for(int i=first[x];i;i=nxt[i]){
int y=go[i],z=w[i];
if(dd[y]>dd[x]+z){
dd[y]=dd[x]+z;
q.push(make_pair(-dd[y],y));
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
e[i]=(node){a,b,c};
add(a,b,c);
}
long long ans=0;
dijkstra1(1);
memset(nxt,0,sizeof(nxt));//链式前向星要初始化
memset(go,0,sizeof(go));
memset(first,0,sizeof(first));
for(int i=1;i<=m;i++)add(e[i].b,e[i].a,e[i].c);
dijkstra(1);
for(int i=1;i<=n;i++){
ans+=dd[i]+d[i];
}
printf("%lld",ans);
return 0;
}
```