1818. 最短路径2

煤渣2333

解决重边问题:使用邻接表存储图

首先是邻接矩阵的问题

  • 刚刚楼上大神的测试用例说明了邻接矩阵会碰到重边的问题
  • 主要是常规的存储图的方法会将重边覆盖
重边覆盖的问题
  • 如果只是常规的重边覆盖,那我们直接选用最短的边不就好了
  • 但是这个题目的问题在于要记录最短路径的数目,也就前面大神说的问题。

使用vector存储邻接表

  1. 可以把重边都记录下来
  2. 使用结构体表示边,和边的终点

下面是代码

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 110, inf = 999999999;

typedef struct edge {                             /* 边的结构体 */
    edge (int x, int y = inf) {                   /* 构造函数 */
        next = x;
        len = y;
    }
    int next, len = inf;
} edge;

vector<edge> g[MAX];
int dist[MAX];
int num[MAX];
bool visited[MAX];
int n, m;

int findm() {                          
    int min = -1, mindist = inf;
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && dist[i] < mindist) {
            min = i;
            mindist = dist[i];
        }
    }
    return min;
}

void dijkstra() {
    dist[1] = 0;
    num[1] = 1;
    while (true) {
        int v = findm();
        if (v == -1) break;
        visited[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            int w = g[v][i].next;
            if (!visited[w]) {
                if (dist[w] > dist[v] + g[v][i].len) {
                    dist[w] = dist[v] + g[v][i].len;
                    num[w] = num[v];
                } else if (dist[w] == dist[v] +g[v][i].len) num[w] += num[v];
            }
        }
    }
}

int main() {
    fill(dist, dist + MAX, inf);
    cin >> n >> m;
    while (m--) {
        int v, w, d;
        scanf("%d %d %d", &v, &w, &d);
        edge t(w, d);                             /* 构造邻边 */
        g[v].push_back(t);                        /* 将边push入结点V的邻接表 */
    }
    dijkstra();
    if (dist[n] != inf) printf("%d %d\n", dist[n], num[n]);
    else printf("-1 0\n");
    return 0;
}
10142130260

重边神坑,这里是测试数据。
测试数据一:
5 9
1 2 1
2 3 1
1 3 2
3 4 2
4 5 1
3 5 3
1 5 10
2 4 3
2 5 4

答案:
5 6

测试数据二:
5 9
1 2 1
2 3 1
1 3 2
3 4 2
4 5 1
3 5 3
1 5 10
3 5 3
3 5 3

答案:
5 8

可以看到,第二组中出现了3次同样的边,
我一开始按照没重边做,后来按照即使有重边也消除影响按一条边做,还是错。
本题目是按照不同继续算,相当于A地与B地有3条长度一样的道路。那么B与C有一条路,则A到C就有3种路径。

10162100357

重边神坑,这里是测试数据。
hhhhh

clysto
#include <bits/stdc++.h>

#define ll   long long
#define SIZE 1000001

using namespace std;

int n, m, u, v, w;
bool visited[SIZE] = {false};
int D[SIZE] = {INT_MAX};
bool S[SIZE] = {false};
int NUM[SIZE] = {0};
map<int, map<int, int>> G;
map<int, map<int, int>> T;

int get_min_index() {
    int min = INT_MAX;
    int min_index = -1;
    for (int i = 1; i <= n; ++i) {
        if (!S[i] && D[i] < min) {
            min = D[i];
            min_index = i;
        }
    }
    return min_index;
}

void dijkstra() {
    D[1] = 0;
    NUM[1] = 1;
    for (int i = 2; i <= n; ++i) {
        D[i] = INT_MAX;
    }

    for (;;) {
        int min_index = get_min_index();
        if (min_index < 0) {
            break;
        }
        int min = D[min_index];
        S[min_index] = true;
        for (int i = 1; i <= n; ++i) {
            if (!S[i] && G[min_index].count(i) && D[i] > min + G[min_index][i]) {
                D[i] = min + G[min_index][i];
                NUM[i] = NUM[min_index] * T[min_index][i];
            } else if (!S[i] && G[min_index].count(i) && D[i] == min + G[min_index][i]) {
                NUM[i] += NUM[min_index] * T[min_index][i];
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        if (G[u].count(v)) {
            T[u][v] += 1;
        } else {
            G[u][v] = w;
            T[u][v] = 1;
        }
    }
    dijkstra();
    cout << (D[n] == INT_MAX ? -1 : D[n]) << " " << NUM[n] << endl;
    return 0;
}
欢迎访问我的主页!http://godweiyang.com

1818题解
//Dijkstra求最短路,再加上cnt数组记录最短路条数,注意重边!用num数组记录重边数量。最坑的是我一直看成了无向图。。。无限WA
[em:03][em:03][em:03][em:03][em:03]

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;

int v[maxn], d[maxn], w[maxn][maxn], cnt[maxn], num[maxn][maxn];
int n, e;

void Dijkstra(int v0)
{
memset(v, 0, sizeof(v));
for (int i = 0; i < n; ++i)
{
d[i] = (i == v0 ? 0 : INF);
cnt[i] = (i == v0 ? 1 : 0);
}
for (int i = 0; i < n; ++i)
{
int x, m = INF;
for (int y = 0; y < n; ++y)
if (!v[y] && d[y] <= m)
m = d[x=y];
v[x] = 1;
for (int y = 0; y < n; ++y)
if (!v[y])
{
if (d[x] + w[x][y] == d[y])
cnt[y] += cnt[x] * num[x][y];
else
if (d[x] + w[x][y] < d[y])
{
cnt[y] = cnt[x] * num[x][y];
d[y] = d[x] + w[x][y];
}
}
}
}

int main()
{
cin >> n >> e;
memset(num, 0, sizeof(num));
for (int i = 0; i < maxn; ++i)
for (int j = 0; j < maxn; ++j)
w[i][j] = INF;
int a, b, p;
while (e–)
{
scanf(“%d%d%d”, &a, &b, &p);
w[a-1][b-1] = p;
num[a-1][b-1]++;
}
Dijkstra(0);
if (d[n-1] == INF)
d[n-1] = -1;
cout << d[n-1] << ” ” << cnt[n-1] << endl;
return 0;
}

10152130220

1818题解
稳的一比

Kevin_K

,.

你当前正在回复 博客/题目
存在问题!