include map include cstdio include fstream include iomanip include str

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <map>
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <sstream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
#define mp make_pair
#define pb push_back
//typedef int int;
typedef pair<pair<int, int>, int> MYTP;
struct edge{
int to, w, maxbeg, end;
int add;
edge(){}
edge( int to, int w, int maxbeg, int end, int add): to(to), w(w), maxbeg(maxbeg), end(end), add(add) {}
};
const int MAXN = 111;
const int MAXT = 155;
int INF = (int)2e9;
int dist[MAXN][MAXT];
int dist2Datk[MAXN];
vector<vector<edge> > g;
int main(){
ios_base::sync_with_stdio(false);
ifstream cin("input.txt");
ofstream cout("output.txt");
int N, M, T, A, B;
for (int i = 0; i < MAXN; ++i)
fill(dist[i], dist[i] + MAXT, INF);
cin >> N >> M >> T >> A >> B;
--A; --B;
fill(dist2Datk, dist2Datk + MAXN, MAXT);
g.resize(N + 1, vector<edge>(0));
for (int i = 0; i < M; ++i){
int fr, to, k;
cin >> fr >> to >> k;
--fr; --to;
vector< pair <int, int> > v;
for (int j = 0; j < k; ++j){
int l, t;
cin >> l >> t;
if (v.empty() || v.back().second != t){
v.push_back(mp(l, t));
} else {
v.back().first += l;
}
}
bool ok = true;
int w = 0;
for (int j = 0; ok && j < (int)v.size(); ++j){
w += v[j].first;
if (v[j].first > T && v[j].second == 1){
ok = false;
}
}
if (v[0].second == 0) dist2Datk[fr] = 0;
else dist2Datk[fr] =min( v[0].first, dist2Datk[fr]);
if (v.back().second == 0) dist2Datk[to] = 0;
else dist2Datk[to] =min( v.back().first, dist2Datk[to]);
if (!ok) continue;
int a, b;
a = (v[0].second == 1)? v[0].first : 0;
b = (v.back().second == 1)? v.back().first : 0;
int add;
if (v.size() == 1 && v[0].second == 1) add = 1;
else add = 0;
edge te(to, w, a, b, add);
g[fr].push_back(te);
te = edge(fr, w, b, a, add);
g[to].push_back(te);
}
dist[A][0] = 0;
priority_queue<MYTP, vector<MYTP>, greater<MYTP> > q;
q.push(mp(mp(0, 0), A));
while (!q.empty()){
int v = q.top().second;
int w = q.top().first.first;
int t = q.top().first.second;
q.pop();
if (t <= T){
//cout << v + 1<< ' ' << w << ' ' << t << endl;
for (int i = 0; i < (int)g[v].size(); ++i){
edge& e = g[v][i];
if (t + e.maxbeg <= T){
int nextd = w + e.w;
int nextt = e.end + e.add * t;
if (nextt <= T && nextd < dist[e.to][nextt]){
dist[e.to][nextt] = nextd;
q.push(mp(mp(nextd, nextt), e.to));
}
}
}
}
w += dist2Datk[v] * 2;
t = dist2Datk[v];
if (t <= T){
//cout << v + 1<< ' ' << w << ' ' << t << endl;
for (int i = 0; i < (int)g[v].size(); ++i){
edge& e = g[v][i];
if (t + e.maxbeg <= T){
int nextd = w + e.w;
int nextt = e.end + e.add * t;
if (nextt <= T && nextd < dist[e.to][nextt]){
dist[e.to][nextt] = nextd;
q.push(mp(mp(nextd, nextt), e.to));
}
}
}
}
}
int ans = INF;
for (int t = 0; t <= T; ++t)
ans = min(ans, dist[B][t]);
if (ans == INF) ans = -1;
cout << ans << endl;
return 0;
}