ZOJ1027 Travelling Fee(DP+SPFA)

给一张有向无环图,边都有花费,从某点到某点走的那条路径上的那一条花费最多的边可以省掉,问从起点到终点的最少花费的多少,

往DP想的话,就可以写出这个状态dp[u][mx],表示到达u点已经省掉的花费为mx的最少花费。

用SPFA更新转移方程。。或者理解成队列+我为人人的转移。。其实这题这样子也能解有环图。

看了别人博客,发现还有三种解法:

  1. 枚举每一条边作为省掉的边,n次SPFA。这方法简洁,可惜想不出= =
  2. 跑Dijkstra,根据记录到每一点时的最长边更新,正确性不懂。。
  3. Floyd+DP:加个维度,dpk[0\1][u][v],第一维1和0分别表示省和没省最长边的最少花费,dp[1]的转移就是dp[1][u][v]=min(dp[0][u][k]+dp[1][k][v],dp[1][u][k]+dp[0][k][v]),初始dp[1][i][j]=0(<i,j>∈E),好厉害。。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 #include<string>
 6 #include<algorithm>
 7 using namespace std;
 8 #define INF (1<<29)
 9 int n,G[222][222];
10 int d[222][10001];
11 bool vis[222][10001];
12 struct Node{
13     int u,mx;
14     Node(int _u,int _mx):u(_u),mx(_mx){}
15 };
16 void SPFA(int vs){
17     for(int i=0; i<n; ++i){
18         for(int j=0; j<10001; ++j) d[i][j]=INF;
19     }
20     d[vs][0]=0;
21     memset(vis,0,sizeof(vis));
22     vis[vs][0]=1;
23     queue<Node> que;
24     que.push(Node(vs,0));
25     while(!que.empty()){
26         Node nd=que.front(); que.pop();
27         int u=nd.u,mx=nd.mx;
28         for(int v=0; v<n; ++v){
29             if(G[u][v]==INF) continue;
30             if(G[u][v]>mx && d[v][G[u][v]]>d[u][mx]+mx){
31                 d[v][G[u][v]]=d[u][mx]+mx;
32                 if(!vis[v][G[u][v]]){
33                     vis[v][G[u][v]]=1;
34                     que.push(Node(v,G[u][v]));
35                 }
36             }
37             if(d[v][mx]>d[u][mx]+G[u][v]){
38                 d[v][mx]=d[u][mx]+G[u][v];
39                 if(!vis[v][mx]){
40                     vis[v][mx]=1;
41                     que.push(Node(v,mx));
42                 }
43             }
44         }
45         vis[u][mx]=0;
46     }
47 }
48 int main(){
49     string name[222],x[111],y[111],vs,vt;
50     int m,z[111];
51     while(cin>>vs>>vt){
52         n=0;
53         scanf("%d",&m);
54         for(int i=0; i<m; ++i){
55             cin>>x[i]>>y[i]>>z[i];
56             name[n++]=x[i]; name[n++]=y[i];
57         }
58         sort(name,name+n);
59         n=unique(name,name+n)-name;
60         for(int i=0; i<n; ++i){
61             for(int j=0; j<n; ++j) G[i][j]=INF;
62         }
63         for(int i=0; i<m; ++i){
64             int u=lower_bound(name,name+n,x[i])-name,v=lower_bound(name,name+n,y[i])-name;
65             G[u][v]=z[i];
66         }
67         SPFA(lower_bound(name,name+n,vs)-name);
68         int tv=lower_bound(name,name+n,vt)-name;
69         int res=INF;
70         for(int i=0; i<10001; ++i) res=min(res,d[tv][i]);
71         printf("%d\n",res);
72     }
73     return 0;
74 }
时间: 02-27

ZOJ1027 Travelling Fee(DP+SPFA)的相关文章

UVA 10497 - Sweet Child Makes Trouble(DP+高精度)

题目链接:10497 - Sweet Child Makes Trouble 题意:n个物品,原来物品属于一个地方,现在要把物品重新放回去,问能放几种使得每个物品都与原来位置不同 思路:递推,一开始随便搞了个二维状态,dp[i][j]表示i个物品,有j个位置不同,那么dp[n][n]就是答案,递推式为: dp[i][j] = 1 (j == 0) dp[i][j] = (j - 1) * dp[i - 1][j - 1] + dp[i - 1][j] + (i - j + 1) * dp[i -

UVA 10641 - Barisal Stadium(DP + 几何)

题目链接:10641 - Barisal Stadium 题意:逆时针给定n个点,在给m个灯,每个灯有一个花费,要求最小花费使得所有边能被灯照到 思路:用向量叉积判断向量的顺逆时针关系,从而预处理出每个灯能照到的边,然后由于n个点是环的,所以可以直接扩大两倍,dp时候去枚举起点即可 状态为dp[i]表示现在照到i条边之前的边全部照亮需要的最小花费 代码: #include <stdio.h> #include <string.h> const double eps = 1e-6;

HDU 2577 How to Type(dp题)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2577 解题报告:有一个长度在100以内的字符串,并且这个字符串只有大写和小写字母组成,现在要把这些字符串用键盘输入到电脑中,一开始的时候大写锁定是关闭的,并且要求结束的时候也是关闭的,然后让你求输入这些字符串最少需要按多少次键盘(包括Cap Lock键和Shift键) 一个典型的dp题,定义一个一维数组就够了,然后dp[i]的含义的输入到第i个字符时需要按键的最少次数.然后递推公式如下: dp[i]

矩形嵌套-记忆化搜索(dp动态规划)

矩形嵌套 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描写叙述 有n个矩形,每个矩形能够用a,b来描写叙述,表示长和宽. 矩形X(a,b)能够嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度).比如(1,5)能够嵌套在(6,2)内,但不能嵌套在(3,4)中. 你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每个矩形都能够嵌套在下一个矩形内. 输入 第一行是一个正正数N(0<N<10).表示測试数据组

POJ 1015 Jury Compromise(dp坑)

提议:在遥远的国家佛罗布尼亚,嫌犯是否有罪,须由陪审团决定.陪审团是由法官从公众中挑选的.先随机挑选n个人作为陪审团的候选人,然后再从这n个人中选m人组成陪审团.选m人的办法是:控方和辩方会根据对候选人的喜欢程度,给所有候选人打分,分值从0到20.为了公平起见,法官选出陪审团的原则是:选出的m个人,必须满足辩方总分和控方总分的差的绝对值最小.如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同,那么选辩控双方总分之和最大的方案即可. 题解:开始想到的是二维01背包,因为评价差的总分值最大可能

Hdu 3336 Count the String(DP+KMP)(好题)

题意:对于长度为len的字符串,我们知道它包含有len个前缀,现在要你统计出这个字符串里面,包含这些前缀的总个数. 思路:这题可以运用KMP的next数组来解,不过也太难想了吧orz,为了用next解这题想那么多也不算是很好的方法orz. 如何根据next数组的性质来解这道题,next数组的值是当前子串的后缀与前缀匹配的个数,所以根据这个性质把题待求的对象改一下:求每种字母作为结尾的串在原串中出现的次数.从最后一个字母分析,首先字符串本身就是以last字母作结,next[last]=x,所以又找

CodeChef STRSUB(dp+二分)

题意:(中文题意) https://codechef_shared.s3.amazonaws.com/download/translated/MARCH15/mandarin/STRSUB.pdf 解析: 先预处理一个数组pre[],pre[i]表示i这个位置,往前最多能找到哪个位置是满足0和1都不大于k的. 然后以每个位置i为左区间的长度就可以计算出,为 (r - pre[i] + 1) 利用这个在预处理一个前缀和数组dp[]. dp[i]表示:从1到i有多少个子串是满足的题目所给的条件. 注

hustwinterC - Happy Matt Friends(dp解法)

Description Matt has N friends. They are playing a game together. Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less

codevs 1173 最优贸易(DP+SPFA运用)

/* 中国的题目 ——贱买贵卖 0.0 这题wa了好多遍 第一遍看着题 哎呀这不很简单嘛 从起点能到的点都是合法的点 然后统计合法的点里最大最小值 然后printf 也不知道哪里来的自信 就这么交了 然后爆零了 第二遍想了想 恩 刚开始思路有问题 必须先买后卖 买的点要在卖的前面 恩 很有道理 然后数组模拟着统计了一下i之前的最小值和i之后的最大值 并且确保每个点都是合法的 然后 连样例都不对了..... 第三遍 终于找到了问题的关键(好吧我是看到标签里有spfa才想到了) 因为他是图啊 图啊