-
Notifications
You must be signed in to change notification settings - Fork 0
/
1074 - Extended Traffic.cpp
78 lines (77 loc) · 1.57 KB
/
1074 - Extended Traffic.cpp
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
//1074 - Extended Traffic
//Dept. ICE, NSTU-11 Batch
#include<bits/stdc++.h>
using namespace std;
//#define INF 99999999
#define INF 1<<28
#define ll long long
#define SZ 100009
#define MX 100000000
#define sfint(a) scanf("%d",&a)
#define sfint2(a,b) scanf("%d%d",&a,&b)
#define sfint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define forlp0(i,n) for(int i=0;i<n;i++)
#define forlp1(i,n) for(int i=1;i<=n;i++)
#define forlpa(i,a,n) for(int i=a;i<=n;i++)
#define rvforlp(i,n) for(int i=n-1;i>=0;i--)
typedef pair<int,int> PII;
#define SIZE 500005
struct edge{
int u,v,w;
};
vector<edge>E;
int dist[500];
int busy[500];
void bellmanford(int source,int n){
forlp0(i,n+1)
dist[i]=INF;
dist[source]=0;
int size=E.size();
forlp0(i,n-1){
forlp0(j,size){
if(dist[E[j].v] > dist[E[j].u]+E[j].w && dist[E[j].u]!=INF){
dist[E[j].v] = dist[E[j].u]+E[j].w;
}
}
}
forlp0(j,size){
if(dist[E[j].v] > dist[E[j].u]+E[j].w && dist[E[j].u]!=INF){
dist[E[j].v] = -INF;
}
}
}
int main()
{
int testCase;
sfint(testCase);
forlp1(i,testCase){
memset(busy,0,sizeof busy);
vector<edge>e; swap(e,E);
int n,m,q,dest;
sfint(n);
forlp1(j,n){
sfint(busy[j]);
}
sfint(m);
forlp1(j,m){
int source,dest;
sfint2(source,dest);
edge test;
test.u=source;
test.v=dest;
test.w=((busy[dest]-busy[source])*(busy[dest]-busy[source])*(busy[dest]-busy[source]));
E.push_back(test);
}
sfint(q);
printf("Case %d:\n",i);
bellmanford(1,n);
forlp1(j,q){
sfint(dest);
if(dist[dest]<3 || dist[dest]==INF)
printf("?\n");
else
printf("%d\n",dist[dest]);
}
}
return 0;
}