2019icpc西安邀请赛

M

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define endl 'n'
const double pi = acos(-1);
const int maxn = 1e5 + 10;
const int maxm = 2e7 + 10;
const ll mod = 1e9 + 7;
int n, m, c, d, e, cnt;
int head[maxn], vis[maxn];
struct node{
int to;
int next;
int quan;
}edge[maxn << 1];
struct nod{
int u, dis, dep, key;
bool operator< (const nod& xgd) const{
return key > xgd.key;
}
}ans[maxn];
void add(int u, int v, int w){
edge[cnt].to = v;
edge[cnt].quan = w;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
int main(){
int u, v, w;
scanf("%d %d", &n, &m);
scanf("%d %d %d", &c, &d, &e);
memset(head, -1, sizeof(head));
for(int i = 1 ; i <= m ; ++ i){
scanf("%d %d %d", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
priority_queue<nod> que;
for(int i = 1 ; i <= n ; ++ i) ans[i].key = INF;
ans[1].key = 0;
que.push(nod{1, 0, 0, 0});
while(!que.empty()){
//puts("44");
nod cur = que.top();
que.pop();
int u = cur.u;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u] ; i != -1 ; i = edge[i].next){
int v = edge[i].to;
int diss = max(edge[i].quan, ans[u].dis);
int depp = ans[u].dep + 1;
int keyy = max((diss + d - 1) / d, (depp + e - 1) / e);
if(keyy < ans[v].key){
ans[v].key = keyy; ans[v].u = v;
ans[v].dis = diss; ans[v].dep = depp;
que.push(nod{v, diss, depp, keyy});
}
}
}
cout << ans[n].key * c << endl;
return 0;
}
/*
5 7
1 1 1
1 2 1
1 3 5
1 4 1
2 3 2
2 4 5
3 4 3
3 5 5
*/

最后

以上就是迷人西牛为你收集整理的2019icpc西安邀请赛的全部内容，希望文章能够帮你解决2019icpc西安邀请赛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。