概述

一道最短路的水题，，，尽量不看以前的代码打出来，，，熟悉一下dijkstra的格式和链式前向星的写法，，，，

虽然是水题，，，但是一开始没考虑取费用最短的wa了一发，，，，QAQ

分析

链式前向星存图，，再加一个数组保存源点到每个点的费用cst[maxm]，，，注意取最少的费用

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int maxn = 1e3 + 10;

const int maxm = 1e5 + 10;

const int inf = 0x3f3f3f3f;

int head[maxm << 1];

bool vis[maxn];

int dis[maxm];

int cst[maxm];

int cnt;

int n , m;

struct edge

{

    int to;

    int w;

    int c;

    int last;

}edge[maxm << 1];

void addedge(int u , int v , int w , int c)

{

    edge[cnt].to = v;

    edge[cnt].w = w;

    edge[cnt].c = c;

    edge[cnt].last = head[u];

    head[u] = cnt++;

}

struct node

{

    int u;

    int w;

    node(int _u , int _w):u(_u) , w(_w){}

    bool operator < (const node &res) const

    {

        return w > res.w;

    }

};

void dijkstra(int n , int s)

{

    for(int i = 1; i <= n; ++i)

        dis[i] = (i == s) ? 0 : inf;

    memset(cst , inf , sizeof cst);cst[s] = 0;

    memset(vis , false , sizeof vis);

    priority_queue<node> q;

    while(!q.empty())   q.pop();

    q.push(node(s , 0));

    while(!q.empty())

    {

        node x = q.top();q.pop();

        int u = x.u;

        if(vis[u])  continue;

        vis[u] = true;

        for(int i = head[u] ; ~i; i = edge[i].last)

        {

            int to = edge[i].to;

            int w = edge[i].w;

            int c = edge[i].c;

            if(!vis[to] && dis[u] + w <= dis[to])

            {

                dis[to] = dis[u] + w;

                //if(cst[u] + c < cst[to])

                    cst[to] = cst[u] + c;

                q.push(node(to , dis[to]));

            }

        }

    }

}

int main()

{

    while(scanf("%d%d" , &n , &m) && n && m)

    {

        cnt = 0;

        memset(head , -1 , sizeof head);

        int u , v , w , c;

        for(int i = 1; i <= m; ++i)

        {

            scanf("%d%d%d%d" , &u , &v , &w , &c);

            addedge(u , v , w , c);

            addedge(v , u , w , c);

        }

        int s , t;

        scanf("%d%d" , &s , &t);

        dijkstra(n , s);

        printf("%d %d\n" , dis[t] , cst[t]);

    }

}

//最短路相等时注意取费用最短的

//

//5 7

//1 2 5 5

//2 3 4 5

//1 3 4 6

//3 4 2 2

//3 5 4 7

//4 5 2 4

//1 3 4 4

//1 5

//8 10

差不多记住了的dijkatra的代码，，，继续继续

(end)

秒客网

hdu-3790最短路刷题

概述

分析

代码

相关文章