专栏首页用户6093955的专栏【(图) 旅游规划 (25 分)】【Dijkstra算法】

【(图) 旅游规划 (25 分)】【Dijkstra算法】

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 500;
const int INF = 0x3f3f3f3f;
struct Road
{
    int _len;
    int _cost;
}road[maxn][maxn];
int vis[maxn];
struct City
{
    int _len;
    int _cost;
}d[maxn];
int N, M, S, D;
void init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            road[i][j]._len = INF, road[i][j]._cost = INF;
    for(int i = 0; i < N; i++)
        d[i]._len = INF, d[i]._cost = INF;
    d[S]._len = 0;
    d[S]._cost = 0;
}
void solve()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= N; i++)
    {
        int x, minlen = INF;
        for(int j = 0; j < N; j++)
        {
            if(!vis[j] && d[j]._len < minlen)
            {
                minlen = d[j]._len;
                x = j;
            }
        }
        vis[x]  = 1;
        if(minlen == INF)
            break;
        for(int y = 0; y < N; y++)
        {
            if(!vis[y])
            {
                if(d[y]._len > d[x]._len + road[x][y]._len)
                {
                    d[y]._len = d[x]._len + road[x][y]._len;
                    d[y]._cost = d[x]._cost + road[x][y]._cost;
                }
                else if(d[y]._len == d[x]._len + road[x][y]._len)
                    d[y]._cost = min(d[y]._cost, d[x]._cost + road[x][y]._cost);
            }
        }
    }
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d %d %d %d", &N, &M, &S, &D);
    init();
    int a, b, c, dd;
    for(int i = 0; i < M; i++)
    {
        scanf("%d %d %d %d", &a, &b, &c, &dd);
        road[a][b]._len = road[b][a]._len = c;
        road[a][b]._cost = road[b][a]._cost = dd;
    }
    solve();
    printf("%d %d\n", d[D]._len, d[D]._cost);
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Integer Inquiry UVA-424(大整数)

    _DIY
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 2011 Google Code Jam 小记

    好久没写这种类型的代码,感觉真是退步了很多。 这是我第一次参加Google Code Jam,以前有过报名可是没有做过。 我发现Google Code Ja...

    owent
  • 汉诺塔II

    用户7727433
  • BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

    首先不难想到拓扑排序,但是直接对原图按\(k\)从小到大拓扑排序是错的。因为当前的\(k\)大并不意味着后面的点\(k\)也大

    attack
  • HUST 1017 Exact cover(DLX精确覆盖)

           题意是给了n*m的01矩阵,选择最少的行,使得每一列都恰好包含一个1,然后输出这些行

    Ch_Zaqdt
  • Integer Inquiry UVA-424(大整数)

    _DIY
  • BZOJ4010: [HNOI2015]菜肴制作(拓扑排序 贪心)

    attack
  • Java的标签

    以前笔者如何退出双重循环呢? 利用循环条件判断,加上break、continue、return可以改变流程

    晚上没宵夜

扫码关注云+社区

领取腾讯云代金券