P8802 [蓝桥杯 2022 国 B] 出差

分析

很明显：单源最短路径 + 没有负权边 = dijkstra

1.存图

2.准备两个数组

dis[]：更新源点到各个点的距离

vis[]：标记是否访问

3.从源点开始，更新源点到与其邻接的点的距离，每次选出dis[]min且未访问的点进行重复上述步骤

代码

两种实现方法：

1.链式前向星存图 + prioroty_queue

注意：优先队列默认大根堆，故要重载 < ;且优先队列按优先级排序，对于 < 而言，a < b为true的意思是，右边的优先级大于左边，故应为return a > b;

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;typedef long long ll;
const int N = 1010,M = 10010;
struct Node{int u,dis;//重载 <(优先队列默认大根堆)bool operator < (const Node &x)const{return dis > x.dis;}
};
//链式前向星
struct edges{int to;int ne;int w;
}e[M*2];
int head[N],cnt = 1,n,m,c[N];
ll dis[N];
bool vis[N];
priority_queue<Node> q;//初始化
void init()
{memset(head,-1,sizeof head);memset(dis,0x3f,sizeof dis);
}
//加边
void add(int u,int v,int w)
{e[cnt].to = v;e[cnt].ne = head[u];e[cnt].w = w;head[u] = cnt ++;
}
//dijkstra模板
void dijkstra(int x)
{dis[x] = 0;q.push((Node){x,0});while(!q.empty()){Node t = q.top();q.pop();int u = t.u;if(vis[u]) continue;vis[u] = 1;for(int i = head[u];i != -1;i = e[i].ne)  //遍历邻接点{int v = e[i].to;int w = e[i].w;if(dis[v] > dis[u] + w)  //更新dis[]{dis[v] = dis[u] + w;if(!vis[v]) q.push((Node){v,dis[v]});  //未被访问，压入队列}}}
}int main()
{init();scanf("%d %d",&n,&m);for(int i = 1;i <= n;i ++) scanf("%d",&c[i]);for(int i = 1;i <= m;i ++){int u,v,w;scanf("%d %d %d",&u,&v,&w);add(u,v,w + c[v]);  //把隔离时间当边权值add(v,u,w + c[u]);}dijkstra(1);printf("%lld",dis[n] - c[n]);  //减去最后一个城市的隔离时间return 0;
}

2.邻接矩阵存图 + 一重循环（高举y总大旗！超简洁！）

#include<iostream>
#include<cstring>
using namespace std;typedef long long ll;
const int N = 1010;
int g[N][N],n,m,c[N];
ll dis[N];
bool vis[N];void dijkstra()
{memset(dis,0x3f,sizeof dis);dis[1] = 0;//重复分析中的第三步n-1次即可for(int i = 1;i < n;i ++){//找到dis[]中的min且未被访问int t = 0;  //初始化dis[]为0x3f，t = 0时，dis[t] = maxfor(int j = 1;j <= n;j ++){if(!vis[j] && dis[t] > dis[j]) t = j;}//找到t，用t更新dis[]for(int j = 1;j <= n;j ++){if(dis[j] > dis[t] + g[t][j])dis[j] = dis[t] + g[t][j];}vis[t] = true;  //记得标记一下已访问}return ;
}int main()
{memset(g,0x3f,sizeof g);  //初始化g[][]scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++) scanf("%d",&c[i]);for(int i = 1;i <= m;i ++){int x,y,z;scanf("%d%d%d",&x,&y,&z);g[x][y] = z + c[y];g[y][x] = z + c[x];  //存双向边 + c[x]}dijkstra();printf("%lld",dis[n] - c[n]);return 0;
}