dijkstra

【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili

#include
#include
using namespace std ;

const int N = 510 ;
bool st[N] ;
int g[N][N] ;
int d[N] ;
int n , m ;

int dijkstra()
{
    memset(d , 0x3f , sizeof d) ;
    d[1] = 0 ;
    for(int i = 0 ; i < n ; i++)
    {
        int t = -1 ;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!st[j] && (t == -1 || d[t] > d[j])) t = j ;
        }
        st[t] = true ;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!st[j] && d[t] + g[t][j] < d[j]) d[j] = d[t] + g[t][j] ;
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1 ;
    return d[n];
}
int main()
{
    cin >> n >> m ;
    memset(g , 0x3f , sizeof g) ;
    while(m--)
    {
        int a , b , c ;
        cin >> a >> b >> c ;
        g[a][b] = min(g[a][b] , c) ;
    }
    cout << dijkstra() ;
    return 0 ;
}

#include
#include
#include
#include

using namespace std ;

typedef pair PII ;
const int N = 1e5 + 10 ;
int h[N] , e[N] , ne[N] , idx ;
int d[N] , w[N] ;
bool st[N] ;
int n , m ;

void add(int a , int b ,int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++ ;
}
int dijkstra()
{
    memset(d , 0x3f , sizeof d) ;
    priority_queue(PII , vector , greater) heap ;
    d[1] = 0 ;
    heap.push({0,1}) ;
    while(heap.size())
    {
        auto t = heap.top() ;
        heap.pop() ;
        int x = t.first , y = t.second ;
        if(st[y]) continue ;
        st[y] = true ;
        for(int i = h[y] ; i!= -1 ; i = ne[i])
        {
            int j = e[i] ;
            if(x + w[j] < d[j]) d[j] = x + w[j] ;
            heap.push({d[j] , j}) ;
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1 ;
    return d[n] ;
}

int main()
{
    cin >> n >> m ;
    for(int i = 0 ; i < m ; i++)
    {
        int a , b , c ;
        cin >> a >> b >> c ;
        add(a,b,c) ;
    }
    cout << dijkstra() ;
    return 0 ;
}