HDU 2544 shortest path dijkstra&&SPFA_haishengone’s blog

Shortest path Time Limit: 5000/1000 MS (Java/ Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 42695 Accepted Submission(s): 18706 Problem Description In the annual school competition, all students who enter the final will get a very beautiful t-shirt. But every time our staff transports hundreds of pieces of clothes from the store back to the arena, it is very tiring! So now they want to find the shortest route from the store to the arena, can you help them? the input The input includes multiple sets of data. The first line of each set of data is two integers N, M (N<=100, M<=10000), N indicates how many intersections there are on the streets of Chengdu, the intersection marked with 1 is the location of the store, and the intersection marked with N is the location of the venue, and M means that there are several roads in Chengdu. N=M=0 indicates the end of input. Next M lines, each line includes 3 integers A, B, C (1<=A, B<=N, 1<=C<=1000), indicating that there is a road between intersection A and intersection B, we It takes C minutes for the workers to walk this way. Input guarantees that there is at least one…