频道栏目
首页 > 考试 > 其他 > 正文
HDU 6120 - transaction transaction transaction 最短路dij算法
2017-09-12 10:39:35      个评论    来源:litmxs的博客  
收藏   我要投稿

HDU 6120 - transaction transaction transaction 最短路dij算法

题目大意

n个城市, n-1条道路, 给出每条道路的长度, 每公里路费1元, 第i个城市书的价格为pi, 一个商人, 从某个城市出发, 买一本书, 在到另一个城市卖出去, 求最多能赚多少钱

思路

建图, 最短路
设置一个超级源点S, 与每个城市建边, 权值为pi(这个城市书的价格), 和一个超级汇点T, 与每个城市建边, 权值为-pi, 再将有道路相连的城市建边, 权值为道路长度
最后S-T的最短路就是最大受益的负数

代码

1029MS 15944K 1177 B G++

#include 
using namespace std;
const int maxn = 1e5 + 100, inf = 0x3f3f3f3f;
struct edge
{
    int to, cost;
    edge(int a, int b) { to = a, cost = b; }
    edge(){}
};
vector G[maxn];
typedef pair P;
int n, d[maxn];

void dij(int s)
{
    priority_queue, greater

> que; memset(d, inf, sizeof(d)); d[s] = 0; que.push(P(0, s)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto &e : G[v]) { if(d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } void addedge(int u, int v, int cost) { G[u].push_back(edge(v, cost)); } int main() { int T; for(scanf("%d", &T); T; --T) { scanf("%d", &n); for(int i=0; i<=n+1; ++i) G[i].clear(); int s = 0, t = n+1; for(int i=0; i

点击复制链接 与好友分享!回本站首页
上一篇:leetcode240. Search a 2D Matrix II
下一篇:LeetCode:260. Single Number III
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站