欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Vijos - 城市连接(最短路)

程序员文章站 2024-02-24 18:42:16
...

题目链接:https://vijos.org/p/1635

题目描述

天网恢恢,疏而不漏,经过上一次的抓捕,OI总部终于获取了怪盗的特征!现在,我们需要在基德再次来之前就把他的特征送到超级大牛的手上,可惜超级大牛不在总部.所以飞过海必须尽快把资料送到大牛家里.已知OI总部到大牛家中间有n-2个城市,为了尽快达到目的地,飞过海通过水晶球(够先进吧)了解到OI总部到大牛家的路线图,图上显示了n个城之间的连接距离。可是飞过海很忙,需要请你来帮忙写个程序.

输入格式

第1行n,第2行到第n+1行,每行n个数字(第i+1行,表示第i个城市与其他城市之间的连接关系,0表示不连接其他数字表示连接的距离)

输出格式

第1行 n个用空格间隔的整数 表示所选的线路.
第2行 一个数字 最短距离

样例输入

7
0 3 5 0 0 0 0
0 0 0 7 8 6 0
0 0 0 0 4 5 0
0 0 0 0 0 0 4
0 0 0 0 0 0 7
0 0 0 0 0 0 6
0 0 0 0 0 0 0

样例输出

1 2 4 7
14

限制

各个测试点1s SO ESAY^-^

提示

n<=1000

解题思路

最短路的题,套一下模板就行了,只不过在松弛边的时候记录一下路径就行了。

#include <stdio.h>
#include <string.h>
const int inf = 99999999;
struct edge {
    int u, v, w;
}e[1000010];
int vis[1010], dis[1010], f[1010], p[1010], q[1010], cnt, n;
void Add(int u, int v, int w)
{
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Dijkstra(int s)
{
    int k;
    for (int i = 0; i < n; i++)
    {
        dis[i] = inf;
        vis[i] = 0;
    }
    dis[s] = 0;
    vis[s] = 1;
    for (int i = 0; i < n; i++)
    {
        int min = inf;
        for (int j = 0; j < n; j++)
            if (!vis[j] && min > dis[j])
                min = dis[k = j];
        vis[k] = 1;
        for (int j = f[k]; j; j = e[j].u)
        {
            int v = e[j].v;
            if (e[j].w < inf && !vis[v] && dis[v] > dis[k] + e[j].w)
            {
                p[v] = k;
                dis[v] = dis[k] + e[j].w;
            }
        }
    }
}
int main()
{
    int m, w;
    while (~scanf("%d", &n))
    {
        cnt = 0;
        memset(f, 0, sizeof(f));
        memset(p, -1, sizeof(p));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &w);
                if (!w)
                    Add(i, j, inf);
                else Add(i, j, w);
            }
        Dijkstra(0);
        int k = 0, a = n - 1;
        q[k++] = a + 1;
        while (p[a] != -1)
        {
            a = p[a];
            q[k++] = a + 1;
        }
        for (int i = k - 1; i > 0; i--)
            printf("%d ", q[i]);
        printf("%d\n%d\n", q[0], dis[n - 1]);
    }
    return 0;
}
相关标签: Dijkstra