CSU 1808:地铁(Dijkstra)
2024-09-01 02:16:25
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1808
题意:……
思路:和之前的天梯赛的一题一样,但是简单点。
没办法直接用点去算。把边看成点去做,规定dis[i]为走完第i条边之后即达到edge[i].v这个点的时候需要的花费。
点数为2*m。如果用普通的Dijkstra和SPFA会超时,所以用优先队列优化的Dijkstra。
#include <bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long LL;
const LL INF = 1000000000000000000LL;
struct Edge {
int u, v, nxt, w, c;
} edge[N*];
struct Node {
LL d; int id;
bool operator < (const Node &rhs) const {
return d > rhs.d;
}
};
int head[N], tot, n, m;
bool vis[N*];
LL dis[N*]; void Add(int u, int v, int w, int id) {
edge[tot] = (Edge) { u, v, head[u], w, id}; head[u] = tot++;
edge[tot] = (Edge) { v, u, head[v], w, id}; head[v] = tot++;
} LL Dijkstra() {
for(int i = ; i < tot; i++) dis[i] = INF;
memset(vis, , sizeof(vis));
LL ans = INF;
priority_queue<Node> que;
while(!que.empty()) que.pop(); for(int i = head[]; ~i; i = edge[i].nxt)
que.push((Node) {edge[i].w, i}), dis[i] = edge[i].w;
while(!que.empty()) {
Node now = que.top(); que.pop();
int pree = now.id; LL pred = now.d;
if(vis[pree]) continue; vis[pree] = ;
int u = edge[pree].v;
if(u == n && ans > pred) ans = pred;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int nowe = i;
LL nowd = dis[pree] + edge[nowe].w + abs(edge[nowe].c - edge[pree].c);
if(nowd < dis[nowe] && !vis[nowe]) {
dis[nowe] = nowd;
que.push((Node) { nowd, nowe });
}
}
}
return ans;
} int main() {
while(~scanf("%d%d", &n, &m)) {
memset(head, -, sizeof(head)); tot = ;
for(int i = ; i <= m; i++) {
int u, v, c, w;
scanf("%d%d%d%d", &u, &v, &c, &w);
Add(u, v, w, c);
}
printf("%lld\n", Dijkstra());
}
return ;
}
/*
3 3
1 2 1 1
2 3 2 1
1 3 1 1
3 3
1 2 1 1
2 3 2 1
1 3 1 10
3 2
1 2 1 1
2 3 1 1
*/
最新文章
- Apache Shiro 学习记录4
- SpringMVC学习
- C中的fseek函数使用
- [转]MySQL数据库的优化-运维架构师必会高薪技能,笔者近六年来一线城市工作实战经验
- node express 学习1
- codeforces Round #258(div2) D解题报告
- 关于如何用sql语句查询出连续的一串数字
- JavaEE系列之(一)JSP基础知识详解
- 修改Tomcat内存大小
- Python新手学习基础之数据类型——变量
- docker 中国站 www.dockerpool.com 报价图片下载
- iOS学习——iOS原生实现二维码扫描
- 数据加密算法--详解DES加密算法原理与实现
- 20175306 MyCP博客总结
- 最接近原点的K个点
- 【转】WPF自定义控件与样式(10)-进度控件ProcessBar自定义样
- pymongo操作mongodb
- Java集合和泛型
- Android Studio 3.1.2 版本包下载
- Linux查看文件内容