最短路径（Dijkstra?）

· · 题解

DFS暴力做法

一、实验目标

给定一个无向加权图，1..n个顶点，m条边，请输出任意一条可行的1到n的最短路径。

输入格式：

第一行n和m 接下来m行：每行三个整数u、v、w，表示一个权为w的无向边 输出格式：

一个可行的路径（空格隔开），如果不存在就输出-1

输入样例1：

5 6

1 2 2

2 5 5

2 3 4

1 4 1

4 3 3

3 5 1

输出样例1：

1 4 3 5

数据范围：1<=n、m<=100000

二、分析

  1. 思路 首先输入、使用邻接表建图，然后用dfs计算最短路径，将最短的路径存储起来输出。

路径存储：

a[N]、alast用来存储查找的路径 b[N]、blast用来存储最短路径，在判断最小值时保存起来，最后输出

三、实验步骤

  1. 数据定义、输入、建图
  2. 调用dfs查找最短路径，输出
  3. 实现dfs函数

代码

#include <iostream>
#include<vector>
#define N 15

using namespace std;

struct Edge {
    int y;
    int w;
};

int a[N];
int n, m, last;
int mn = 0x3f3f3f3f;
vector<Edge> g[N];
bool vis[N];
int b[N], blast;

void dfs(int x, int len) {
    if (x == n) {
        if (len < mn) {
            mn = len;
            blast = last;
            for (int i = 1; i <= last; i++)
                b[i] = a[i];
            return;
        }
    }
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i].y, w = g[x][i].w;
        if (vis[y]) continue;
        vis[y] = true;
        a[++last] = y;
        dfs(y, len + w);
        --last;
        vis[y] = false;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        Edge e1 = {y, w};
        g[x].push_back(e1);
        Edge e2 = {x, w};
        g[y].push_back(e2);
    }
    vis[1] = true;
    a[++last] = 1;
    dfs(1, 0);

    for (int i = 1; i <= blast; i++)
        cout << b[i] << " ";
    return 0;
}