单源最短路径(二)

单源最短路的综合应用

(1) 新年好

第一眼，时间复杂度用朴素dijkstra肯定爆炸，只能堆优化版了

这题不是吃甜草的牛那道，每个亲戚可能都不在一条路径上，要找到分支的和，想到找到最短路中最远的一个亲戚，然后不断pre到他的前一个亲戚知道1，如果没有pre到说明不在一条路径上，需要找到没有pre到的点

[!WARNING]

这样想就偏离题意了

#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N=1e5+10;
int h[N],e[N],ne[N],w[N],idx;
int st[N],d[N],pre[N];
int vis[5];

void add(int a,int b,int c){
  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(){
  memset(d,0x3f,sizeof d);
  
  priority_queue<PII,vector<PII>,greater<PII> > q;
  q.push({0,1});
  d[1]=0;
  
  while(q.size()){
    auto t=q.top();
    q.pop();
    
    int ver=t.second,dist=t.first;
    if(st[ver]) continue;
    st[ver]=1;
    
    for(int i=h[ver];i!=-1;i=ne[i]){
      int j=e[i];
      if(d[j]>dist+w[i]){
        d[j]=dist+w[i];
        pre[j]=ver;
        q.push({d[j],j});
        cout<<ver<<' '<<j<<' '<<d[j]<<endl;
      }
    }
  }
}

signed main(){
  cin>>n>>m;
  int a[5];
  memset(h,-1,sizeof h);
  for(int i=0;i<5;i++) cin>>a[i];
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    add(x,y,z);
    add(y,x,z);
  }
  dijkstra();
  int ans=0;
  int end=1;
  //vis[end]=1;
  for(int i=0;i<5;i++){
    int maxn=a[i];
    for(int j=0;j<5;j++){
      if(!vis[a[j]]&&d[a[j]]>d[maxn]){
        maxn=a[j];
      }
    }
    
    cout<<maxn<<' '<<d[maxn]<<endl;
    if(!vis[maxn]){
      end=maxn;
      ans+=d[end];
      //vis[maxn]=1;
    } 
    while(end!=1&&!vis[end]){
      //cout<<end<<' ';
      vis[end]=1;
      end=pre[end]; 
    }
    //cout<<endl;
  }
  
  
  cout<<ans<<endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

仔细分析代码和样例发现，这题和信使(最远最短路)以及牛吃甜草(选一个点到各个点最短距离只和最小)不一样

重新捋一遍思路，发现需要找到一个最优访问亲戚的顺序，那就需要对亲戚的访问顺序做一遍排列

#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int> PII;
int n,m;
//是双向的，M别开小了
const int M=2e5+10,N=5e4+10,INF=0x3f3f3f3f;
int h[M],e[M],ne[M],w[M],idx;
int d[6][N],st[N],vis[N];
int a[6];

void add(int a,int b,int c){
  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u,int start,int distance){
  if(u==6){
    return distance;
  }
  int res=INF;
  for(int i=1;i<=5;i++){
    if(!vis[i]){
      int next=a[i];
      vis[i]=1;
      res=min(res,dfs(u+1,i,distance+d[start][next]));
      vis[i]=0;
    }
  }
  return res;
}

//这里d[]是局部一位数组
void dijkstra(int start,int d[]){
  
  memset(st,0,sizeof st);
  memset(d,0x3f,N*4);
  
  priority_queue<PII,vector<PII>,greater<PII> > q;
  
  q.push({0,start});
  d[start]=0;
  
  while(q.size()){
    auto t=q.top();
    q.pop();
    
    int ver = t.second,dist=t.first;
    
    if(st[ver]) continue;
    st[ver]=1;
    
    for(int i=h[ver];i!=-1;i=ne[i]){
      int j=e[i];
      if(d[j]>dist+w[i]){
        d[j]=dist+w[i];
        q.push({d[j],j});
      }
    }
  }
}

signed main(){
  cin>>n>>m;
  
  memset(h,-1,sizeof h);
  a[0]=1;
  for(int i=1;i<=5;i++) cin>>a[i];
  
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    add(x,y,z);
    add(y,x,z);
  }
  for(int i=0;i<6;i++) dijkstra(a[i],d[i]);
  
  cout<<dfs(1,0,0)<<endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

(2) 通信线路

“指定路径上（1—>N）不超过

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/775011