题意:玩家能量初始值有100,有100个房间,每个房间有一个大于-100小于100的能量值,每个房间与其他一些房间单向联通,玩家走到一个房间后能量加上房间的能量值,房间可以重复进入。若玩家的能量小于等于0,玩家输,若玩家到达终点,玩家赢。 以房间为点,从房间到房间建有向边,边的权值为进入的房间的能量值。求初始点到各点的剩余最大能量,注意如果出现环,要判断这个环是否与终点联通。判断连通性需要用floyd进行预处理。 判环应该用bellman,此题的数据比较弱,用spfa的代码也能AC,但应该是错的。 举个例子:同时出…

2016年4月1日 0条评论 0点热度 阅读全文

Dijkstra:适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV) BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE) SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2, 但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(VE). Floyd:每对节点之间的最短路径。 Bellman-Ford算法 Bellman-Ford算法能在更普遍的情况下(…

2016年3月1日 0条评论 0点热度 阅读全文

Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 39574   Accepted: 14541 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar becau…

2016年2月27日 0条评论 0点热度 阅读全文

Currency Exchange Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 24432   Accepted: 8900 Description Several currency exchange points are working in our city. Let us suppose that each point specializes in two particul…

2016年2月26日 0条评论 0点热度 阅读全文

Silver Cow Party Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 16352 Accepted: 7474 Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow part…

2016年1月14日 0条评论 0点热度 阅读全文

思路:Dijkstra求最短路径,将0节点作为原点,求出到各个点的距离。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define inf 0x3fffffff #define N 1005 int T,S,D,n,map[N][N],vis[N],cast[N],s[N],e[N]; void Dijkstra() { int i,j,minn,pos; me…

2015年11月29日 0条评论 0点热度 阅读全文

最短路径问题 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 17968    Accepted Submission(s): 5385 Problem Description 给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其…

2015年8月20日 0条评论 8点热度 阅读全文

畅通工程续 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。 现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。 Input 本题目包含多组数据,请处理到文件结束。 每组数据第一行包含…

2015年8月5日 0条评论 3点热度 阅读全文

Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗? Input 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1&…

2015年8月5日 0条评论 6点热度 阅读全文

Layout Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7613   Accepted: 3658 Description Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbe…

2015年1月29日 0条评论 0点热度 阅读全文