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

题目描述

旅行是一件颇有趣的事情,但是在旅行前规划好路线也很重要。现在小D计划要去U国旅行。
U国有N个城市,M条道路,每条道路都连接着两个城市,并且经过这条道路需要一定的费用wi。
现在小D想要从u城市到v城市,但是他的汽车需要在途中加一次油(途中包括u和v两个城市)。在每个城市加油都有不同的费用vi。
小D想知道从u城市到v城市最少需要多少费用(经过道路的费用+加油的费用)。
城市从1-n进行编号。

输入格式

第一行两个正整数n,m,表示n个城市,m条无向道路
接下来n行,第i行一个整数vi,表示第i个城市的加油费用
接下来m行,第i行三个整数ai, bi, wi,表示第i条道路连接ai和bi两个城市,经过要花费wi的费用
接下来一个正整数q,表示小D有q个询问
接下来q行,第i行两个整数ui, vi, 表示小D想知道从ui到vi需要的最少费用(ui和vi可能相等)

输出格式

对于每个询问,输出一行整数,表示最小的费用,如果ui不能到达vi,则输出-1

样例输入

3 6
2666
3977
2457
1 2 6920
1 2 276
1 3 839
3 1 3490
2 1 7395
3 1 7540
6
3 2
3 1
2 2
2 1
3 2
2 2

样例输出

3572
3296
3218
2942
3572
3218

限制

每个测试点1s

提示

对于30%的数据,保证n<=10
对于70%的数据,保证n<=80
对于100%的数据,保证n<=300
保证q,m<=n*n, 0 <= wi, vi <= 10000
数据中可能有重边和自环

解题思路

这就是一道最短路题,跑一遍Floyd最短路,求出任意两点的路费,最后在遍历一遍每个顶点,使其在此处加油,找出最小的费用就行了。注意:初始化的时候自己到自己应为0,这个我错了很多遍。。。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int inf = 99999999;
int map[310][310], s[310], n;
void Floyd()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
}
int main()
{
    int u, v, w, m, q, minn;
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    map[i][j] = inf;
                else map[i][j] = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &s[i]);
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            map[u][v] = map[v][u] = min(map[u][v], w);
        }
        Floyd();
        scanf("%d", &q);
        while (q--)
        {
            minn = inf;
            scanf("%d%d", &u, &v);
            for (int i = 1; i <= n; i++)
                minn = min(minn, map[u][i] + map[i][v] + s[i]);
            if (minn < inf)
                printf("%d\n", minn);
            else printf("-1\n");
        }
    }
    return 0;
}