image.png

Dijkstra算法邻接矩阵代码模板 O(n2)

适合图的点数不超过1000的情况

  1. //全局变量部分
  2. const int MAXN = 1000;  //图的最大顶点数
  3. const int INF = 1000000000; //设立INF为一个极大数，
  4.             //这里这个数也可以设置为0x3f3f3f3f,这代表无穷大，即1061109567这一数值
  6. int n;                  //当前图的点数
  7. int vis[MAXN];          //标记数组用于记录图中各个点的被访问情况，0为未访问，1为已访问
  8. int dis[MAXN];          //记录起点到各个顶点的最短路径长度
  9. int m[MAXN][MAXN];      //用一个邻接矩阵来记录图中各个点的连接情况
  11. void Dijkstra(int s){   //s为起点
  12.     fill(vis, vis+MAXN, 0); //将标记数组初始化为0即未被访问状态，此处可用memset
  13.     fill(dis, dis+MAXN, INF);   //将最短路数组初始化为一个很大的数，此处要注意不可用memset
  14.     dis[s]=0;           //首先将起点s到达自身的最短路设为0
  15.     for(int i=0;i<n;i++){   //n次循环，遍历完n个点   
  16.         int node = -1;      //node记录当前能找到的从起点到此没被访问的最短的一个点
  17.         int minn = INF;     //minn记录到达那个点的最短路径
  18.         for(int j=0;j<n;j++){   //每个点逐步寻找没被访问的最短的一个点
  19.             if(vis[j]==0 && dis[j]<minn){   
  20.                 minn = dis[j];
  21.                 node = j;
  22.             }
  23.         }
  24.         if(node==-1){   //找不到小于INF的一个点，说明其他结点与定点不连通
  25.             return ;
  26.         }
  27.         vis[node] = 1;  //将当前点标记为1
  28.         for(int j=0;j<n;j++){
  29.             if(vis[j]==0 && m[node][j]!=INF && (dis[node]+m[node][j])<dis[j]){
  30.                 //如果结点未被访问且 node能到达此结点 并且从起点到此结点过node中介点更近
  31.                 //在此标尺只有距离，如果有两条距离相等或多条相等，那么就只需在此进行修改
  32.                 //如路径相同第二标尺为花费时，则可通过在增加花费数组，在此if后加elseif判断距离相等情况花费不同条件。
  33.                 //下题就有两标尺。
  34.                 dis[j] = dis[node]+m[node][j];
  35.             }
  36.         }
  37.     }
  38. }

二维矩阵+堆优化：个人认为最好写最实用

总结一下，Dijkstra算法的流程就是，不断取出离顶点最近而没有被访问过的点，松弛它和它能到达的所有点。
如何取出离顶点最近的点？如果暴力寻找，那就是朴素的Dijkstra算法，时间复杂度是O^2
但我们可以采取堆优化。具体而言，我们可以用一个优先队列（或手写堆，那样更快）来维护所有节点。这样可以实现 mlogm 的算法

  1. int dis[maxn], vis[maxn] = {0};
  2. vector<pair<int, int>> E[maxn];//存图 <u, d> E[i]到u点距离为d
  3. typeof pair<int ,int> PAIR; //<起点到x点的距离, x>
  4. #define MP make_pair 
  5. priority_queue<PAIR, vector<PAIR>, greater<PAIR>> Q;//距离短的优先级高，也就是 Q.top()
  6. void Dij(int s){
  7.     fill(dis, dis + maxn, INT_MAX);
  8.     fill(vis, vis + maxn, 0);
  9.     dis[s] = 0;
  10.     Q.push(MP(0,s));
  11.     while(!Q.empty()){
  12.         int u = Q.top().second;Q.pop();
  13.         if(vis[u])continue;
  14.         vis[u] = 1;
  15.         for(auto it : E[u]){
  16.             if(dis[it.first] > it.second + dis[u]){
  17.                 dis[it.first] = it.second + dis[u];//更新dis
  18.                 //或许还有其他的操作
  19.             }else if(){}//有时还有其他的判断条件
  20.             if(!vis[it.first]) Q.push(MP(dis[it.first], it.first));
  21.         }
  22.     }    
  23. }

优化：链式前向星+堆优化 O(mlogm)

链式前向星
用一个优先队列（或手写堆，那样更快）来维护所有节点。

  1. typedef pair<int, int> Pair; //<x点到起点的距离, x>
  2. priority_queue<Pair, vector<Pair>, greater<Pair> > Q; // // 这里是greater, 使得距离短的先出队
  5. void Dij(int s) //传入起点编号
  6. {
  7.     fill(vis, vis+MAXN, 0); 
  8.     fill(dis, dis+MAXN, INF); 
  9.     dist[s] = 0;
  10.     Q.push(make_pair(0, s));
  11.     while (!Q.empty())
  12.     {
  13.         int p = Q.top().second;
  14.         Q.pop();
  15.         if (vis[p])
  16.             continue;
  17.         vis[p] = 1;
  18.         for (int e = head[p]; e != 0; e = edges[e].next)
  19.         {
  20.             int to = edges[e].to;
  21.             dist[to] = min(dist[to], dist[p] + edges[e].w);
  22.             if (!vis[to])
  23.                 Q.push(make_pair(dist[to], to));
  24.         }
  25.     }
  26. }

题目

L2-001 紧急救援 (25 分)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int INF = 1e8;
  5. //N<500
  6. int saveTeam[505];//各点的存储的救援人数
  7. int st[505];//按路径能召集到的最多人数
  8. int mm[505][505];//地图
  9. int number[505];//到该点最短路径的数量
  10. int vis[505];//是否标记为node过
  11. int dis[505];//起点到该点的距离
  12. int father[505];//最短路径中，该点的上一个节点
  13. int n,m,s,d;//城市数量、路线数量、起点、终点
  15. void Dijkstra(){
  16.     //初始化
  17.     fill(dis,dis+n,INF);
  18.     fill(vis,vis+n,0);
  19.     fill(number,number+5,0);
  20.     dis[s]=0;
  21.     st[s]=saveTeam[s];
  22.     number[s]=1;
  23.     for(int i=0; i<n;i++){
  24.         int minn = INF,node = -1;
  25.         for(int j =0;j<n;j++){
  26.             if(!vis[j] && dis[j]<minn){
  27.                 minn = dis[j];
  28.                 node = j;
  29.             }
  30.         }
  31.         vis[node]=1;
  32.         if(node == -1)return;
  33.         for(int j =0;j<n;j++){
  34.             if(vis[j]==0 && mm[node][j]!=-1 && (dis[node]+mm[node][j]) <dis[j]){
  35.                 dis[j]=dis[node]+mm[node][j];
  36.                 st[j] = st[node]+saveTeam[j];
  37.                 father[j]=node;
  38.                 number[j] = number[node];
  39.             }else if(vis[j]==0 && mm[node][j]!=-1 && (dis[node]+mm[node][j])==dis[j]){
  40.                 if((st[node]+saveTeam[j]) > st[j]){
  41.                     st[j] = st[node]+saveTeam[j];
  42.                     father[j]=node;
  43.                 }
  44.                 number[j]+=number[node];
  45.             }
  46.         }
  47.     }
  48. }
  50. int main(){
  51.     vector<int> pathV;
  52.     cin>>n>>m>>s>>d;
  53.     for(int i = 0;i<n;i++){
  54.         cin>>saveTeam[i];
  55.     }
  56.     //初始化地图
  57.     for(int i = 0;i<n;i++){
  58.         for(int j = 0;j<n;j++){
  59.             mm[i][j] = -1;
  60.         }
  61.     }
  62.     //读入地图
  63.     for(int i =0;i<m;i++){
  64.         int n1,n2,val;
  65.         cin>>n1>>n2>>val;
  66.         mm[n1][n2]=val;
  67.         mm[n2][n1]=val;
  68.     }
  69.     Dijkstra();
  70.     int p =d;
  71.     while(1){
  72.         if(p==father[p]){//应该是0，即没有father
  73. //         cout<<"pfather"<<p<<" "<<father[p]<<"\n";
  75.             pathV.push_back(p);break;
  78.         }
  79.         pathV.push_back(p);
  80. //         cout<<"pfather"<<p<<" "<<father[p]<<"\n";
  81.         p = father[p];
  82.     }
  83.     cout<<number[d]<<" "<<st[d]<<endl;
  84. //     cout<<pathV.size();
  85.     for(int  i = pathV.size()-1; i>=0;i--){
  86.         if(i==pathV.size()-1){
  87.             cout<<pathV[i];
  88.         }else{
  89.             cout<<" "<<pathV[i];
  90.         }
  91.     }
  92. }

L3-005 垃圾箱分布 (30 分)

题目大意：

  • 从m个垃圾站里面选取1个站点，让他离居民区的最近的人最远，并且没有超出服务范围ds之内。
  • 如果有很多个最远的垃圾站，输出距离所有居民区距离平均值最小的那个。
  • 如果平均值还是一样，就输出按照顺序排列垃圾站编号最小的那个

思路：

  • 垃圾站之间也是彼此有路连接的，最短路径计算也要把垃圾站算上。
  • 所以我们就是对 n+m 个点进行Dijkstra计算最短路径，计算出1~m号垃圾站距离其他站点的最短路径。
  • 遍历dis数组，如果dis存在一个距离大于服务范围ds的距离，那么我们就舍弃这个垃圾站。
  • 取最短的路径，这就是距离它最近的垃圾站mindis。如果mindis > ansdis，更新。

  • G开头的，编号设为n+G后面的数字

    1. #include <cstdio>
    2. #include <algorithm>
    3. #include <iostream>
    4. #include <string>
    5. using namespace std;
    6. const int inf = 999999999;
    7. int n, m, k, ds, station;
    8. int e[1020][1020], dis[1020];
    9. bool visit[1020];
    10. int main() {
    11.   //初始化地图,没路的距离就是inf
    12.   fill(e[0], e[0] + 1020 * 1020, inf);    
    13.   fill(dis, dis + 1020, inf);
    14.   scanf("%d%d%d%d", &n, &m, &k, &ds);
    15.   for(int i = 0; i < k; i++) {
    16.       int tempdis;
    17.       string s, t;
    18.       cin >> s >> t >> tempdis;
    19.       int a, b;
    20.       //注意处理字符串//这样处理最后一个点会错误——没注意是小于“等于”10情况...
    21. //         if(s[0] == 'G') {
    22. //             a = s[1] - '0' + n;
    23. //         } else {
    24. //             a = stoi(s);
    25. //         }
    26. //         if(t[0] == 'G') {
    27. //             b = t[1] - '0' + n;
    28. //         } else {
    29. //             b = stoi(t);
    30. //         }
    31.       if(s[0] == 'G') {
    32.           s = s.substr(1);
    33.           a = n + stoi(s);
    34.       } else {
    35.           a = stoi(s);
    36.       }
    37.       if(t[0] == 'G') {
    38.           t = t.substr(1);
    39.           b = n + stoi(t);
    40.       } else {
    41.           b = stoi(t);
    42.       }
    44.       //将数据添入地图
    45.       e[a][b] = tempdis;
    46.       e[b][a] = tempdis;
    47.   }
    49.   int ansid = -1;//存储最终选择的候选编号，如果没有符合要求的 就是-1
    50.   double ansdis = -1,  //最终的最短路径
    51.          ansaver = inf;//最终的平均路径长度
    53.   //对每个候选点进行dij算法：将其作为起点，算出到各个居民的距离——存储在dis中
    54.   for(int index = n + 1; index <= n + m; index++) {
    55.       double mindis = inf, //候选点到各个居民的路径中最短的长度
    56.              aver = 0; //该候选点到各点的平均长度
    57.       fill(dis, dis + 1020, inf); //重置dis
    58.       fill(visit, visit + 1020, false); //重置vis
    59.       dis[index] = 0; //起点到自身距离自然为0
    60.       for(int i = 0; i < n + m; i++) {
    61.           int u = -1, //本轮距离起点最近的点
    62.               minn = inf;//最近距离
    63.           for(int j = 1; j <= n + m; j++) {
    64.               if(visit[j] == false && dis[j] < minn) {
    65.                   u = j;
    66.                   minn = dis[j];
    67.               }
    68.           }
    69.           if(u == -1) break;//没其他点能到起点了
    70.           visit[u] = true;
    71.           for(int v = 1; v <= n + m; v++) {
    72.               if(visit[v] == false && dis[v] > dis[u] + e[u][v])
    73.                   dis[v] = dis[u] + e[u][v];
    74.           }
    75.       }
    76.       for(int i = 1; i <= n; i++) {
    77.           if(dis[i] > ds) { //有距离过远，不符合题意
    78.               mindis = -1;
    79.               break;
    80.           }
    81.           if(dis[i] < mindis) mindis = dis[i]; //最短路径
    82.           aver += 1.0 * dis[i];
    83.       }
    84.       if(mindis == -1) continue;
    85.       aver = aver / n;
    87.       //判断一下
    88.       if(mindis > ansdis) {
    89.           ansid = index;
    90.           ansdis = mindis;
    91.           ansaver = aver;
    92.       } else if(mindis == ansdis && aver < ansaver) {
    93.           ansid = index;
    94.           ansaver = aver;
    95.       }
    96.   }
    97.   if(ansid == -1)
    98.       printf("No Solution");
    99.   else {
    100.       printf("G%d\n", ansid - n);
    101.       printf("%.1f %.1f", ansdis, ansaver);//输出一位小数
    102.   }
    103.   return 0;
    104. }

    L3-011 直捣黄龙

  • 三个条件：最快>城镇最多>有效杀伤最多

  • 存储：最合适路径、最快路数、最短进攻距离、歼敌总数
  • 数据量：城镇数∈[2, 200]
  • 将字符串与数字做映射，方便操作
  • Dijskra
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define FOR(i, n, m) for (int i = n; i < m; ++i)
  6. struct node
  7. {
  8.     int id, dis;
  10.     //方便后面的优先队列
  11.     bool friend operator<(const node &a, const node &b)
  12.     {
  13.         return a.dis > b.dis;
  14.     }
  15. };
  17. int n, k, s, t, cnt, d,
  18.     enemyNum[205], //各个大本营敌军数量
  19.     enemyAll[205], //到该点的总共的歼敌数量
  20.     pre[205],       //到该大本营的上一个点
  21.     Dis[205],       //起点到各点的最短距离
  22.     vis[205],
  23.     sum[205],         //到该点路线数量
  24.     liberation[205]; //到该店解放的大本营数
  26. //映射
  27. map<string, int> ntoi; //name->id
  28. map<int, string> iton; //id->name
  30. vector<pair<int, int>> E[205]; //存图, <u,d>:E[i]到u点,权为d
  31. vector<int> ans;
  32. string S, T, u, v;
  34. void Dijskra()
  35. {
  36.     fill(Dis, Dis + 205, 1e9);
  37.     Dis[s] = 0;
  38.     sum[s] = 1;
  39.     priority_queue<node> Q;
  40.     Q.push(node{s, 0});
  41.     while (!Q.empty())
  42.     {
  43.         int now = Q.top().id, nowD = Q.top().dis;
  44.         Q.pop();
  45.         if (vis[now])
  46.             continue;
  47.         vis[now] = 1;
  48.         for (auto it : E[now])
  49.         {
  50.             int itV = it.first, itD = it.second;
  51.             if (Dis[itV] > nowD + itD)
  52.             {
  53.                 Dis[itV] = nowD + itD;
  54.                 enemyAll[itV] = enemyAll[now] + enemyNum[itV];
  55.                 sum[itV] = sum[now];
  56.                 liberation[itV] = liberation[now] + 1;
  57.                 Q.push(node{itV, Dis[itV]});
  58.                 pre[itV] = now;
  59.             }
  60.             else if (Dis[itV] == nowD + itD)
  61.             {
  62.                 sum[itV] += sum[now];
  63.                 if (liberation[itV] < liberation[now] + 1)
  64.                 {
  65.                     liberation[itV] = liberation[now] + 1;
  66.                     enemyAll[itV] = enemyAll[now] + enemyNum[itV];
  67.                     Q.push(node{itV, Dis[itV]});
  68.                     pre[itV] = now;
  69.                 }
  70.                 else if (liberation[itV] == liberation[now] + 1)
  71.                 {
  72.                     if (enemyAll[itV] < enemyAll[now] + enemyNum[itV])
  73.                     {
  74.                         enemyAll[itV] = enemyAll[now] + enemyNum[itV];
  75.                         Q.push(node{itV, Dis[itV]});
  76.                         pre[itV] = now;
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.     }
  82. }
  83. int main()
  84. {
  85.     ios::sync_with_stdio(false);
  86.     cin >> n >> k >> S >> T;
  87.     for (int i = 0; i < n - 1; i++)
  88.     {
  89.         cin >> u >> d;
  90.         ntoi[u] = ++cnt;
  91.         iton[cnt] = u;
  92.         enemyNum[cnt] = d;
  93.     }
  94.     //起点的映射
  95.     ntoi[S] = 0, iton[0] = S;
  96.     //终点
  97.     t = ntoi[T];
  99.     for (int i = 0; i < k; i++)
  100.     {
  101.         cin >> u >> v >> d;
  102.         //存边
  103.         E[ntoi[u]].push_back({ntoi[v], d});
  104.         E[ntoi[v]].push_back({ntoi[u], d});
  105.     }
  106.     Dijskra();
  107.     d = t;
  108.     while (d)
  109.     {
  110.         ans.push_back(d);
  111.         d = pre[d];
  112.     }
  113.     cout << iton[0];
  114.     for (int i = ans.size() - 1; i >= 0; i--)
  115.     {
  116.         cout << "->" << iton[ans[i]];
  117.     }
  118.     cout << "\n"
  119.          << sum[t] << " " << Dis[t] << " " << enemyAll[t] << "\n";
  120.     return 0;
  121. }