(Step6.2.3) HDU 2544 (the shortest circuit -the shortest path)

2023-03-18

Title: Enter two integer n, m. The number of villages and roads is respectively represent. In the next M lines, there are 3 integer, A, B, C. The starting point and end point of this road, and the time required from the starting point to the end point. Special, 1 means a commodity store. N also means the game venue. Ask the staff from the starting point to the end point

problem -solving ideas:

1) Make start = 1, end = n. To

code is as follows:

``````#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;
#define inf 10000000000000

__int64 map[101][101];
__int64 d[101];
__int64 hash[101];
__int64 a[101];
__int64 l1,l2,l3,l4,c1,c2,c3,c4;
__int64 n,m;
__int64 start,end;

struct node{
__int64 weight;
node* next;
};

struct Heap{

bool operator<(Heap T)const{
return T.dis < dis;
}
__int64 x;
__int64 dis;
};

priority_queue<Heap> Q;

__int64 bfs(){
__int64 i;
for(i = 0 ; i <= n ; ++i){
hash[i] = 0;
d[i] = inf;
}

Heap min,in;
while(!Q.empty()){
Q.pop();
}

in.x = start;
in.dis = 0;
d[start] = 0;
Q.push(in);
while(!Q.empty()){
min = Q.top();
Q.pop();

if(min.x == end){
return min.dis;
}

if(hash[min.x]){
continue;
}

hash[min.x] = true;

for(i = 1 ; i<= n ; ++i){\
if(d[i] > d[min.x] + map[min.x][i] && !hash[i]){
in.x = i;
in.dis = map[min.x][i] + d[min.x];
d[i] = in.dis;
Q.push(in);
}
}
}
return -1;
}

int judge(int dis){

return 0;
}

int main(){
while(scanf("%I64d%I64d",&n,&m),n){
__int64 i,j;
for(i = 0 ; i <= n ; ++i){
for(j = 0 ; j <= n ; ++j){
map[i][j] = inf;
}
}

for(i = 0 ; i < m ; ++i){
__int64 a,b,c;
scanf("%I64d%I64d%I64d",&a,&b,&c);
if(map[a][b] > c){
map[a][b] = map[b][a] = c;
}
}

start = 1;
end = n;
bfs();

if(d[end] == inf){
printf("i'm so soryy!\n");
}else{
printf("%d\n",d[end]);
}
}
}
``````

source