Algorithms/Dijkstra.cpp at master · abdullah-sust/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//dijkstra_by_myself
//non-directed graph.....
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define s scanf
#define p printf
#define ll long long int
vector<ll >ver[50];
vector<ll >cost[50];
ll  par[50],dist[50];
struct data
{
    ll  address,dis;
    data(ll  a,ll  b)
    {
        address=a;
        dis=b;
    }
    bool operator<(const data &x)const
    {
        return dis<x.dis;
    }
};
ll  dijkstra(ll  start,ll  end)
{
    dist[start]=0;
    priority_queue<data>q;

    ll  sz,u,v,i;
    q.push(data(start,dist[start]));
    while(!q.empty())
    {
        data temp=q.top();
        q.pop();
        u=temp.address;
        //v=temp.dis;
        if(u==end)
        return dist[end];
        sz=ver[u].size();
        for(i=0;i<sz;++i)
        {
            v=ver[u][i];
            ll  t=dist[u]+cost[u][i];
            if(dist[v]>t)
            {
                dist[v]=t;
                q.push(data(v,dist[v]));
                par[v]=u;
            }
        }
    }
    return -1;
}
int  main()
{
    ll  a,b,c,d,e,n,i,j,k,start,end,ans;
    while(s("%lld %lld",&n,&e)==2)
    {
        for(i=1;i<=e;++i)
        {
            s("%lld %lld %lld ",&a,&b,&c);
            ver[a].push_back(b);
            ver[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);
        }
        memset(par,0,sizeof(par));
        memset(dist,63,sizeof(dist));
        s("%lld %lld",&start,&end);
        ans=dijkstra(start,end);

        if(ans==-1)
        p("Impossible.\n");
        else
        p("Minimum distance is: %lld\n",ans);
        for(i=1;i<=n;++i)
        {
            ver[i].clear();
            cost[i].clear();
        }
    }
    return 0;
}
/*
Input:
5 6
1 3 10
1 2 25
1 3 40
2 5 50
3 5 50
4 5 70
1 5
output:
Minimum distance is: 75
*/