题面

描述：

N cities (2 ≤ N ≤ 10 000 ) are connected by a network of M one-way roads (1 ≤ M <100 000 000 ). It is known that these roads do not cross outside the cities. The numeration of the cities and the roads starts from 1.There is at most one road from any city to another one. The length of each road does not exceed 10 000 .

The company for which you work sends you on a business trip from city 1 to city N on your personal car. The trip expenses will be compensated to you only if the distance you drive will differ from the shortest possible by no more than K (0 ≤ K ≤ 10 000).

The task is to determine on which roads you can drive to have the right to the compensation. That means the list of all roads that appear on at least one route from city 1 to city N where the length of the route does not exceed the length of the shortest route by more than K.

输入：

The input consists of M+1 lines. The first line contains the numbers N, M, and K. Each next line describes one road and contains the initial city number, the final city number and the length of the road. All numbers are integers and separated from each other by one or more spaces.

输出：

The output consists of several lines. The first line contains the integer L – the number of roads you can use. The following L lines contain the numbers of the roads in ascending order.

样例输入：

1
2
3
4
5
6
4 5 1
1 2 1
1 3 4
2 3 1
2 4 3
3 4 1

样例输出：

1
2
3
4
5
4
1
3
4
5

题目大意：

给出一个有 n 个点 m 条边的有向图，每条边有一定的长度，你从点 1 出发去 n 出差。公司规定，当你从点 1 到 n 走的路程长度不超过 1 到 n 的最短路长度加 K 时，你才可以获得报销。现在问题就是让你求哪些边是可以走的（就是说通过这条边，至少有一条从 1 到 n 的，长度不超过最短路长度加 K 的路径。

输入是一个图，然后按从小到大的编号输出可走的边。

废话不多说，解释都放在代码里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
 * Almost the shortest route
 * POJ-3554
 *
 * 由于此题网上无题解,此处解释一下思路:
 * 由于要考虑经过某一条边是否可行,
 * 例如边 e <a, b, d>, 若要判断经过 e 是否可行, 则考虑:
 * 1 -> a -> b -> N 是否可行,
 * 此时需求出 1 -> a, b -> N 的最短路,
 * 所以需要跑两趟最短路, 以 1 为起点 和 以 N 为起点, 然后枚举边去判断
 * 因为是有向图,所以需要建两个图,一个正向图一个反向图.
 */

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;

struct edge {
  int u, dist, id;

  bool operator<(const edge& t) const { return dist > t.dist; }
};

vector<edge> vt1[maxn];  //正向图
vector<edge> vt2[maxn];  //反向图

int d1[maxn];
int d2[maxn];
bool vis[maxn];
int n, m, k;

template <typename _Tp>  //读入优化
void read(_Tp& x) {
  int f = 1;
  x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = x * 10 + s - '0';
    s = getchar();
  }
  x *= f;
}

void dijkstra(int s, int d[], vector<edge> vt[]) {  // 最短路，相信大家都懂
  memset(vis, 0, sizeof(vis));
  memset(d, inf, sizeof(d) * maxn);
  d[s] = 0;
  priority_queue<edge> q;
  q.push(edge{s, 0, 0});
  while (!q.empty()) {
    edge e = q.top();
    q.pop();
    int u = e.u;
    if (vis[u]) {
      continue;
    }
    vis[u] = true;
    for (int i = 0; i < vt[u].size(); i++) {
      int v = vt[u][i].u;
      int dist = d[u] + vt[u][i].dist;
      if (dist < d[v]) {
        d[v] = dist;
        q.push(edge{v, d[v], 0});
      }
    }
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int f, t, dist;
    read(f);
    read(t);
    read(dist);
    vt1[f].push_back(edge{t, dist, i});  // 建立正向图
    vt2[t].push_back(edge{f, dist, i});  // 建立反向图
  }
  dijkstra(1, d1, vt1);
  dijkstra(n, d2, vt2);
  vector<int> ans;
  int len = d1[n];
  for (int i = 1; i <= n; i++) {  // 枚举边去判断
    for (int j = 0; j < vt1[i].size(); j++) {
      int a = i, b = vt1[i][j].u;
      int dist = vt1[i][j].dist;
      if (d1[a] + d2[b] + dist <= len + k) {
        ans.push_back(vt1[i][j].id);
      }
    }
  }
  sort(ans.begin(), ans.end());  // 记得排序
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}