问题 A: 赛艇表演

时间限制: 3 Sec 内存限制: 256 MB
提交: 93 解决: 33
[提交] [状态] [命题人:admin]
题目描述
小明去某个地区观看赛艇比赛，这个地区共有n个城市和m条道路，每个城市都有赛艇比赛，在第i个城市观看赛艇表演的价钱为ai， 去其他城市观看也需要支付赛艇表演的价格。任意两个城市之间通过一条公路连接，并且道路是双向通行的， 观看赛艇比赛时经过的每一条道路都要支付一定的过路费，观看完比赛返回家时经过的每一条道路也要支付过路费。
对于每个城市u，你需要为小明确定一个城市v，使得从u出发，前往v看赛艇表演，再从v回到u，u可以等于v，要求花费的总金额尽量的少。请根据题目给出的数据输出总金额。
输入
第一行两个正整数n和m。
接下来m行，每行三个正整数u，v，w，表示有一条双向道路连接u和v，且每经过一次的过路费是w。 接下来一行n个数，第i个数表示在第i个城市观看赛艇表演的价钱。
输出
输出一行n个数，第i个数表示从第i个城市出发至少要花多少钱
样例输入 Copy
4 2
1 2 4
2 3 7
6 20 1 25
样例输出 Copy
6 14 1 25
提示
对于前30%的数据，n<=10，m<=20。
对于前50%的数据，n<=100，m<=500。
对于前70%的数据，n<=1500，m<=2000。
对于前85%的数据，图的结构以某种方式随机生成。
对于100%的数据，n<=2e5，m<=2e5，过路费和门票钱都在[1,1e12]内。

总结：这题求的是每个点到其他点的最短距离，包括来回的路费和当前结点的费用，可以先把每个点的费用都压入优先队列，那么执行优先队列的时候就相当于求每个点到其他点的最短距离。

这个也可以算是图里每个点到其他点的最短距离。

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N = 2e5+10;
const int inf = 0x3f3f3f3f;struct str{int dot;ll dis;int next;
}e[N<<5];
int head[N<<5];
ll w[N],dis[N];
int n,m,cnt,vis[N];
priority_queue<P,vector<P>,greater<P> >que;void dijkstra(){while(!que.empty()){P t = que.top();que.pop();if(vis[t.second] == 1) continue;vis[t.second] = 1;for(int i = head[t.second];i;i = e[i].next){int v = e[i].dot;ll W = e[i].dis;if(dis[v] > W+t.first){dis[v] = W+t.first;if(!vis[v])que.push(P(dis[v],v));}}}
}
void add(int x,int y,ll z){e[++cnt].dot = y;e[cnt].dis = z;e[cnt].next = head[x];head[x] = cnt;
}
int main(){scanf("%d%d",&n,&m);while(m--){int x,y;ll z;scanf("%d%d%lld",&x,&y,&z);add(x,y,z*2);add(y,x,z*2);}for(int i = 1;i <= n;i++){scanf("%lld",dis+i);que.push(P(dis[i],i));}dijkstra();for(int i = 1;i <= n;i++){printf("%lld ",dis[i]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！