NOWCODER 吃火锅(单源最短路dijkstra（）算法)

admin管理员组

文章数量:1035056

NOWCODER 吃火锅(单源最短路dijkstra（）算法)

链接：
来源：牛客网

题意：

有n个城市，m条双向道路。
第i条路线可用于从城市v[i]到城市u[i]（以及从u[i]到v[i]），需要花费wi。
每个城市都开了一个相同的火锅店，但价格不同，第i个店吃的花费是val[i]。
要计算每个城市的人最少的吃火锅花费（花费包括来回的路费和吃火锅的费用，留在自己的城市不用路费）。

思路：

我们可以把火锅店里的花费val也看成一条路径的边权，也就是加一个超级原点
设这个超级原点初始到每个城市的火锅店的路径花费为val，也就是这个城市的火锅店里的花费
原先的城市间的路径花费变为原来的两倍（因为是来回路径）
那么每个城市的人吃火锅的最小花费就简化成了超级原点到每个城市的最小花费的问题
最短路问题，一般情况下有dijkstra和floyed,考虑到floyed时间复杂度 O （ n 3 ) O（n^3) O（n3)会超时。。。
我们从超级原点跑一遍单源最短路就可以了，求出的最短距离就是这个城市的人吃火锅的最小花费

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
struct Edge { //邻接表 int to,next;ll w;
} e[maxn*3];
struct Node {int id;ll dis;
};
ll n,m,u,v,w,tot=1,val,head[maxn],dis[maxn];
void add(ll u,ll v,ll w) {e[tot].to=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;
}
void dijkstra() {//迪杰斯特拉算法 memset(dis,0x3f,sizeof(dis));dis[0]=0;queue<Node> q;q.push(Node {0,0ll});while(!q.empty()) {Node now = q.front();q.pop();for(int i=head[now.id]; i; i = e[i].next) {if(dis[now.id]+e[i].w<dis[e[i].to]) {//松弛dis[e[i].to]=dis[now.id]+e[i].w;q.push(Node {e[i].to,dis[e[i].to]});}}}
}
int main() {cin>>n>>m;for(int i=0; i<m; i++) {cin>>u>>v>>w;add(u,v,2*w),add(v,u,2*w);}for(int i=1; i<=n; i++) {cin>>val;add(0,i,val);}dijkstra();for(int i=1; i<=n; i++) {cout<<dis[i]<<(i==n? "\n": " ");}
}

NOWCODER 吃火锅(单源最短路dijkstra（）算法)

链接：
来源：牛客网

题意：

有n个城市，m条双向道路。
第i条路线可用于从城市v[i]到城市u[i]（以及从u[i]到v[i]），需要花费wi。
每个城市都开了一个相同的火锅店，但价格不同，第i个店吃的花费是val[i]。
要计算每个城市的人最少的吃火锅花费（花费包括来回的路费和吃火锅的费用，留在自己的城市不用路费）。

思路：

我们可以把火锅店里的花费val也看成一条路径的边权，也就是加一个超级原点
设这个超级原点初始到每个城市的火锅店的路径花费为val，也就是这个城市的火锅店里的花费
原先的城市间的路径花费变为原来的两倍（因为是来回路径）
那么每个城市的人吃火锅的最小花费就简化成了超级原点到每个城市的最小花费的问题
最短路问题，一般情况下有dijkstra和floyed,考虑到floyed时间复杂度 O （ n 3 ) O（n^3) O（n3)会超时。。。
我们从超级原点跑一遍单源最短路就可以了，求出的最短距离就是这个城市的人吃火锅的最小花费

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
struct Edge { //邻接表 int to,next;ll w;
} e[maxn*3];
struct Node {int id;ll dis;
};
ll n,m,u,v,w,tot=1,val,head[maxn],dis[maxn];
void add(ll u,ll v,ll w) {e[tot].to=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;
}
void dijkstra() {//迪杰斯特拉算法 memset(dis,0x3f,sizeof(dis));dis[0]=0;queue<Node> q;q.push(Node {0,0ll});while(!q.empty()) {Node now = q.front();q.pop();for(int i=head[now.id]; i; i = e[i].next) {if(dis[now.id]+e[i].w<dis[e[i].to]) {//松弛dis[e[i].to]=dis[now.id]+e[i].w;q.push(Node {e[i].to,dis[e[i].to]});}}}
}
int main() {cin>>n>>m;for(int i=0; i<m; i++) {cin>>u>>v>>w;add(u,v,2*w),add(v,u,2*w);}for(int i=1; i<=n; i++) {cin>>val;add(0,i,val);}dijkstra();for(int i=1; i<=n; i++) {cout<<dis[i]<<(i==n? "\n": " ");}
}

本文标签： NOWCODER 吃火锅(单源最短路dijkstra（）算法)