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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
trueint from,to,val;
trueEdge(int from,int to,int val):from(from),to(to),val(val) {}
};
struct Node
{
trueint x,cnt;
trueNode(int x=0,int cnt=0):x(x),cnt(cnt) {}
};
vector<Edge> node[1010];
int dist[1010][1010];
int n,m;
bool flag[1010][1010];
queue<Node> q;
void SPFA()
{
truememset(flag,false,sizeof(flag));
truememset(dist,INF,sizeof(dist));
trueq.push(Node(1,0));
truedist[1][0] = 0;
truewhile (!q.empty())
true{
truetrueNode v = q.front();
truetrueq.pop();
truetrue
truetruefor (int i = 0; i<node[v.x].size(); i++)
truetrue{
truetruetrueif (dist[ node[v.x][i].to ][ v.cnt+1 ] > dist[v.x][v.cnt] + node[v.x][i].val)
truetruetrue{
truetruetruetruedist[ node[v.x][i].to ][ v.cnt+1 ] = dist[v.x][v.cnt] + node[v.x][i].val;
truetruetruetrueif (!flag[node[v.x][i].to][v.cnt+1] && v.cnt+1<=n)
truetruetruetrue{
truetruetruetruetrueflag[ node[v.x][i].to ][v.cnt+1] = true;
truetruetruetruetrueq.push( Node(node[v.x][i].to, v.cnt + 1) );
truetruetruetrue}
truetruetrue}
truetrue}
truetrueflag[v.x][v.cnt] = false;
true}
}
int main()
{
truecin >> n >> m;
truefor (int i = 0; i<m; i++)
true{
truetrueint x,y,z;
truetruecin >> x >> y >> z;
truetruenode[x].push_back(Edge(x,y,z));
truetrue
true}
trueSPFA();
trueint q;
truecin >> q;
truefor (int i = 1; i<=n; i++)
true{
truetruefor (int j = 1; j<=n; j++)
truetrue{
truetruetruedist[i][j] = min(dist[i][j], dist[i][j-1]);
truetruetrue
truetrue}
truetrue
true}
truewhile (q--)
true{
truetrueint x,y;
truetruecin >> x >> y;
truetruey++;
truetrueif (dist[x][y]!=INF)
truetruetruecout << "=] " << dist[x][y] << endl;
truetrueelse cout << "=[" << endl;
true}
}
|