Jobdu-1341-艾薇儿的演唱会[最短路径] | Acm之家


九度-1341-艾薇儿的演唱会[最短路径] | Acm之家
艾薇儿今天来到了中国,她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况,演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京,她需要找出一条从北京到哈尔滨耗时最短的线路,以便尽快到达哈尔滨。
中国的铁路线非常复杂,有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间,但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗?找出来的人可以免费获得现场演唱会门票一张哦。
输入:
 输入的第一行包括一个整数N(2<=N<=100),代表艾薇儿手上拿到的设有铁路站点的城市的个数,其中城市从1到n进行编号。以及M(1<=M<=1000),代表有M条铁路线路,每条铁路线路只连接两个城市。
接下来的一行有两个数,a和b(1<=a,b<=N),分别表示北京和哈尔滨的编号。
接下来有M行,每行有三个数x,y(1<=x,y<=N),t(1<=t<=1000),表示从城市x到城市y所需时间为t。
输出:
 请输出艾薇儿从北京到哈尔滨最少需要多长时间。你可以放心地认为肯定存在一条路线可以从北京到哈尔滨。
样例输入:

3 4
1 3
1 2 1
3 2 3
2 3 4
3 1 8 
样例输出:
4
提示:
 1.火车能从城市x到城市y,就能从城市y到城市x,并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行,则不同火车从x到y或者从y到x所花费的时间可能不相同。
2.虽然城市数有N个,但不保证所有的城市都能互相到达。可以保证的是,从北京到哈尔滨一定会有一条通路
其实这种题目最难的不是这个算法,而是一些小细节。他的提示里有说:火车能从城市x到城市y,就能从城市y到城市x,并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行,则不同火车从x到y或者从y到x所花费的时间可能不相同。 说明一个路线可能会出现两次,我们要选择最小的那一次。不仅这道题,最短路径的题目很多都有这个隐含的小细节,坑了我多少次。。

08void Dijkstra()
09{
10        int i, j, k, min;
11        for(i = 1; i <= n; ++i)
12                spand[i] = map[s][i];
13        visit[s] = 1;
14        spand[s] = 0;
15        for(i = 2; i <= n; ++i)
16        {
17                k = -1, min = INF;
18                for(j = 1; j <= n; ++j)
19                {
20                        if(!visit[j] && spand[j] < min)
21                        {
22                                k = j;
23                                min = spand[j];
24                        }
25                }
26                if(k == -1)
27                        break;
28                visit[k] = 1;
29                for(j = 1; j <= n; ++j)
30                {
31                        if(!visit[j] && spand[k] + map[k][j] < spand[j])
32                                spand[j] = spand[k] + map[k][j];
33                }
34        }
35        printf("%d\n",spand[e]);
36}
37 
38int main()
39{
40        while(scanf("%d%d%d%d", &n,&m,&s,&e) != EOF)
41        {
42                int i, j;
43                memset(map, 0x3f, sizeof(map));
44                memset(spand, 0x3f, sizeof(spand));
45                memset(visit,0,sizeof(visit));
46                int x, y, t;
47                while(m--)
48                {
49                        scanf("%d%d%d", &x,&y,&t);
50                        if(map[x][y] > t)
51                                map[x][y] = map[y][x] = t;
52                }
53                Dijkstra();
54        }
55        return 0;
56}
Read full article from 九度-1341-艾薇儿的演唱会[最短路径] | Acm之家

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts