NEERC17 J Journey from Petersburg to Moscow
2024-08-21 13:47:09
CF上可以提交。 链接
依然是很妙的解法。
我们可以枚举每一个出现过的边权$L$,然后把所有边的边权减掉这个$L$,如果小于$L$就变为$0$,然后跑一遍最短路然后加上$k * L$更新答案即可。
注意$L$也可以取到$0$。
这样做就是强制让出了前$k$大的边的边权,所以能计算到所有答案。
时间复杂度$O(n^2logn)$。
Code:
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, int> pin; const int N = ;
const ll inf = 0x3f3f3f3f3f3f3f3f; int n, m, K, vCnt = , tot = , head[N];
ll eVal[N], dis[N];
bool vis[N]; struct Edge {
int to, nxt;
ll val;
} e[N << ]; inline void add(int from, int to, ll val) {
e[++tot].to = to;
e[tot].val = val;
e[tot].nxt = head[from];
head[from] = tot;
} template <typename T>
inline void read(T &X) {
X = ; char ch = ; T op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline ll max(ll x, ll y) {
return x > y ? x : y;
} template <typename T>
inline void chkMin(T &x, T y) {
if(y < x) x = y;
} priority_queue <pin> Q;
void dij(ll nowL) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, , sizeof(vis));
Q.push(pin(dis[] = 0LL, ));
for(; !Q.empty(); ) {
int x = Q.top().second; Q.pop();
if(vis[x]) continue;
vis[x] = ;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to; ll val = max(0LL, e[i].val - nowL) + dis[x];
if(val < dis[y]) {
dis[y] = val;
Q.push(pin(-dis[y], y));
}
}
}
} int main() {
read(n), read(m), read(K);
for(int i = ; i <= m; i++) {
int x, y; ll v;
read(x), read(y), read(v);
add(x, y, v), add(y, x, v);
eVal[++vCnt] = v;
}
eVal[++vCnt] = 0LL; sort(eVal + , eVal + + vCnt);
vCnt = unique(eVal + , eVal + + vCnt) - eVal - ; ll ans = inf;
for(int i = ; i <= vCnt; i++) {
dij(eVal[i]);
chkMin(ans, dis[n] + 1LL * K * eVal[i]);
} printf("%lld\n", ans);
return ;
}
最新文章
- 在linux平台实现atosl
- css预处理器sass使用教程(多图预警)
- LintCode Edit Distance
- XML学习笔记1——概述
- Dijkstra最短路径算法实例
- jQuery页面滚动监听事件及高级效果插件
- acdream 1093 女神的正多面体
- hdu 4565 So Easy!(矩阵+快速幂)
- UVaLive 6608 Cabin Baggage (水题)
- WinForm实现跨进程通信的方法
- uva 10780
- CF 33B String Problem
- JDK源码阅读(一) ArrayList
- Sql2008中使用DataTable作为存储过程的参数
- jiaocheng https://github.com/CarpenterLee/JCFInternals
- phpcms:二、头部尾部包含
- VB短信猫开发包,支持超长短信
- XSLT 调用外部程序
- onload=";fixImage(this, 200, 200)";
- CSS3中很容易混淆的transform,translate,transition。如何去区分,以及综合写法。
热门文章
- CS0016: 未能写入输出文件“c:\Windows\Microsoft.NET\Framework\....\App_Web_default.aspx.cdcab7d2.zii776dc.dll”--“拒绝访问。 ”
- HashMap源码分析(基于JDK1.6)
- 转: 使用Jmeter创建ActiveMQ JMS POINT TO POINT请求,环境搭建、请求创建、插件安装、监听服务器资源等
- shell中字体变色
- 73个word使用终极技巧
- Avalon总线概述
- Linux Skills
- MongoDB部署实战(一)MongoDB在windows平台分片集群部署
- 【转】Jmeter JDBC请求的问题
- Tomcat下WebSocket最大连接数测试