Moderator: Board moderators
Code: Select all
#include<stdio.h>
#include<math.h>
#define INF 99999999
typedef struct Edge{
int u,v,w;
} Edge;
Edge edge[20000];
int cost[210];
int v,E;
int d[210];
int n_c[210];
void main(void){
int i,j,k,m,q,count=0;
while(scanf("%d",&v)==1){
count++;
for(i=1;i<=v;i++) scanf("%d",&cost[i]);
scanf("%d",&E);
for(i=0;i<E;i++){
scanf("%d %d",&edge[i].u,&edge[i].v);
edge[i].w=(int)pow((cost[edge[i].v]-cost[edge[i].u]),3.0);
}
for(j=1;j<=v;j++){
d[j]=INF;
n_c[j]=0;
}
d[1]=0;
for(j=0;j<v-1;j++){
for(k=0;k<E;k++){
if(d[edge[k].v]>d[edge[k].u]+edge[k].w) d[edge[k].v]=d[edge[k].u]+edge[k].w;
}
}
for(j=0;j<v-1;j++){
for(k=0;k<E;k++){
if(d[edge[k].v]>d[edge[k].u]+edge[k].w) n_c[edge[k].v]=1;
}
}
scanf("%d",&q);
printf("Set #%d\n",count);
for(i=0;i<q;i++){
scanf("%d",&m);
if(d[m]<3) puts("?");
else if(n_c[m]==1) puts("?");
else if(d[m]==INF) puts("?");
else if(d[m]>=3 && d[m]!=INF) printf("%d\n",d[m]);
}
}
}
Code: Select all
Finally Accepted
I just solve it using modified BFS( surely using queue( not priority_queue)).Dominik Michniewski wrote:I still got WA ....
Could anyone tell me what's maybe wrong or give me some additional test cases ? I become right results for sample input and for Adrian tests ...
Regards
Dominik
Code: Select all
6 6 7 8 9 10 100
6
1 2
2 3
3 4
1 5
5 4
4 5
3
6
4
5Code: Select all
Set #1
?
3
4Code: Select all
Removed after being accepted.
Code: Select all
3 10 1 5
3
1 2
2 3
3 1
1
2
Code: Select all
Set #1
?
Code: Select all
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.Writer;
import java.util.LinkedList;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Queue;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Lokesh Khandelwal
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
Traffic_10449 solver = new Traffic_10449();
solver.solve(1, in, out);
out.close();
}
}
class Traffic_10449 {
public void solve(int testNumber, InputReader in, OutputWriter out) {
String s;
int n, i, m, u, v, q, test = 0;
int limit = (1<<27);
s = in.nextString();
while (s != null) {
test++;
StringTokenizer a = new StringTokenizer(s);
n = Integer.parseInt(a.nextToken());
List<Edge> graph[] = new List[n];
Vertex vertex[] = new Vertex[n];
int busyness[] = new int[n];
for(i=0;i<n;i++) {
vertex[i] = new Vertex(i, limit);
graph[i] = new ArrayList<Edge>();
busyness[i] = Integer.parseInt(a.nextToken());
}
m = in.nextInt();
for(i=0;i<m;i++) {
u = in.nextInt() - 1;
v = in.nextInt() - 1;
if(u >= 0 && v >= 0 && u < n && v < n)
graph[u].add(new Edge(vertex[v], (int)Math.pow(busyness[v] - busyness[u], 3)));
}
GraphUtils.bellmanFord(graph, vertex, 0, n);
boolean isOnNegativeCycle[] = new boolean[n];
for(i=0;i<n;i++) {
for(Edge e : graph[i]) {
if(vertex[i].key + e.cost < e.dest.key) {
isOnNegativeCycle[i] = true;
isOnNegativeCycle[e.dest.index] = true;
}
}
}
boolean visited[] = new boolean[n];
for(i=0;i<n;i++) {
if(!visited[i] && isOnNegativeCycle[i]) {
dfs(i, graph, visited);
}
}
for(i=0;i<n;i++) {
if(visited[i])
isOnNegativeCycle[i] = true;
}
q = in.nextInt();
out.printLine("Set #"+test);
for(i=0;i<q;i++) {
u = in.nextInt() - 1;
if(u < 0 || u >= n || vertex[u].key == limit || isOnNegativeCycle[u] || vertex[u].key < 3) {
out.printLine("?");
}
else out.printLine(vertex[u].key);
}
s = in.nextString();
}
}
public void dfs(int index, List<Edge> graph[], boolean visited[]) {
visited[index] = true;
for(Edge e : graph[index]) {
if(!visited[e.dest.index]) {
dfs(e.dest.index, graph, visited);
}
}
}
}
class InputReader
{
BufferedReader in;
StringTokenizer tokenizer=null;
public InputReader(InputStream inputStream)
{
in=new BufferedReader(new InputStreamReader(inputStream));
}
public String next()
{
try{
while (tokenizer==null||!tokenizer.hasMoreTokens())
{
tokenizer=new StringTokenizer(in.readLine());
}
return tokenizer.nextToken();
}
catch (IOException e)
{
return null;
}
}
public int nextInt()
{
return Integer.parseInt(next());
}
public String nextString()
{
try {
return in.readLine();
}
catch (Exception e)
{
return null;
}
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
class Edge {
public Vertex dest;
public int cost;
public Edge(Vertex dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}
class Vertex implements Comparable<Vertex> {
public boolean visited;
public int parent, key, index, indexInHeap;
public List<Edge> edges;
public Vertex(int index) {
this.index = index;
visited = false;
parent = -1;
key = Integer.MAX_VALUE;
edges = new ArrayList<Edge>();
indexInHeap = index;
}
public Vertex(int index, int key) {
this.index = index;
visited = false;
parent = -1;
this.key = key;
edges = new ArrayList<Edge>();
indexInHeap = index;
}
public int compareTo(Vertex o) {
return this.key - o.key;
}
}
class GraphUtils {
public static void bellmanFord(List<Edge> graph[], Vertex a[], int source, int vertexCount) {
int i, j;
a[source].key = 0;
for(i=0;i<vertexCount-1;i++) { // run loop n-1 times
for(j=0;j<vertexCount;j++) {
for(Edge e : graph[j]) { // relax all edges
if(a[j].key + e.cost < e.dest.key) {
e.dest.key = a[j].key + e.cost;
e.dest.parent = a[j].index;
}
}
}
}
/*check for negative cycle
for(i=0;i<vertexCount;i++) {
for(Edge e : graph[i]) {
if(a[i].key + e.cost < e.dest.key)
return true;
}
}
*/
}
}