我知道不是正解,但我不知道我的代码哪里错了,WA 了三个点,求大佬指点。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
struct Edge {
int to, num, val;
vector<int> v;
Edge (int _to = 0, int _num = 0, int _val = 0) :
to(_to), num(_num), val(_val) {}
};
struct Node {
int u, num;
long long dist;
Node (int _u = 0, int _num = 0, long long _dist = 0) :
u(_u), num(_num), dist(_dist) {}
};
bool operator<(Node x, Node y) {
return x.dist > y.dist;
}
vector<Edge> e[MAXN];
int n, m, k;
int E[MAXN] = {0};
pair<int, int> pos[MAXN];
long long dis[MAXN] = {0};
bool vis[MAXN] = {0};
void Dijkstra(int st) {
memset(dis, 0x3f, sizeof dis);
priority_queue<Node> q;
q.push(Node(st, 0, 0));
dis[st] = 0;
while (!q.empty()) {
int h = q.top().u, nm = q.top().num;
q.pop();
if (vis[h])
continue;
vis[h] = true;
for (int i = 0; i < (int)e[h].size(); i++)
if (!vis[e[h][i].to] && dis[e[h][i].to] > dis[h] + e[h][i].val) {
for (int j = 0; j < (int)e[h][i].v.size(); j++)
if (e[h][i].v[j] > nm) {
dis[e[h][i].to] = dis[h] + e[h][i].val;
q.push(Node(e[h][i].to, e[h][i].v[j], dis[e[h][i].to]));
break;
}
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e[u].push_back(Edge(v, 0, w));
pos[i] = make_pair(u, (int)e[u].size() - 1);
}
for (int i = 1, x; i <= k; i++) {
cin >> x;
e[pos[x].first][pos[x].second].v.push_back(i);
}
Dijkstra(1);
if (dis[n] == 4557430888798830399)
cout << -1;
else
cout << dis[n] << endl;
return 0;
}