最短路径问题(HDOJ 3790)

文章目录[x]
  1. 1:Problem Description
  2. 2:Input
  3. 3:Output
  4. 4:Sample Input
  5. 5:Sample Output
  6. 6:My Code

Problem Description

给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。

Input

输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t) 

Output

 输出 一行有两个数, 最短距离及其花费。 

Sample Input

3 2
1 2 5 6
2 3 4 5
1 3
0 0

Sample Output

9 11 

My Code

题目非常简洁明了,还是中文,真感动,这是一道双花费的最短路的模板,我采用了dijkstra+堆优化的方式,基本上只要把涉及到距离的几个变量,换个名字,用同样的写法写就行了,唯一的不同只是判定是否入队时,和优先队列的排序上有所不同。同样此题用cin会TLE。sync_with_stdio(false)我没试过,应该也能过。

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;

int n, m, s, t;
struct edge
{
    int w;
    int v;
    int p;
    int next;
} e[100010];
struct node
{
    int x, dist, pay;
    friend bool operator<(node a, node b)
    {                           //重载运算符,使距离最短的,花费小的排在队列前面
        if (a.dist == b.dist)
            return b.pay < a.pay;
        else
            return b.dist < a.dist;
    }
};
int tot;
int head[100010];
int dis[1005];
int cost[1005];
bool vis[1005];
void add(int u, int v, int w, int p)
{
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].p = p;
    e[tot].next = head[u];
    head[u] = tot;
}
void dijkstra()
{
    priority_queue<node> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(cost, 0x3f, sizeof(cost));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    cost[s] = 0;
    node tmp;
    tmp.pay = 0;
    tmp.x = s;
    tmp.dist = 0;
    q.push(tmp);
    while (q.size())
    {
        node tmp = q.top();
        q.pop();
        if (vis[tmp.x])
            continue;
        vis[tmp.x] = 1;
        for (int i = head[tmp.x]; i != 0; i = e[i].next)
        {
            if (dis[e[i].v] > dis[tmp.x] + e[i].w || dis[e[i].v] == dis[tmp.x] + e[i].w && cost[e[i].v] > cost[tmp.x] + e[i].p)
            {
                node next;
                next.x = e[i].v;
                next.dist = dis[e[i].v] = dis[tmp.x] + e[i].w;
                next.pay = cost[e[i].v] = cost[tmp.x] + e[i].p;
                q.push(next);
            }
        }
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m) && n && m)
    {
        tot = 0;
        memset(head, 0, sizeof(head));
        for (int i = 0; i < m; i++)
        {
            int u, v, w, p;                     //cin会tle
            scanf("%d%d%d%d", &u, &v, &w, &p);
            add(u, v, w, p);
            add(v, u, w, p);
        }
        scanf("%d%d", &s, &t);
        dijkstra();
        printf("%d %d\n", dis[t], cost[t]);
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00