Page 2 #include <iostream> #include <vector> #include <queue> #define INF (1<<29) using namespace std; struct Arista { int hasta,costo; }; Arista armar(int h,int c) { Arista ar; ar.hasta=h; ar.costo=c; return ar; } struct Grafo { int suma=0; vector <vector <Arista>> adj; vector <int> dist; vector <bool> visitado; bool encontro=false; int nodos,aristas; int S,F; void leer() { cin >> nodos >> aristas; adj.resize(nodos+1); dist.resize(nodos+1,INF); visitado.resize(nodos+1,false); int desde,hasta,costo; for(int c=0; c<aristas; c++) { cin >> desde >> hasta >> costo; adj[desde].push_back(armar(hasta,costo)); } cin >> S >> F; dist[S]=0; } void bdfs(int nodo, int padre) { visitado[nodo]=true;
for(int c=0; c<adj[nodo].size(); c++) { int vecino=adj[nodo][c].hasta; int costo=adj[nodo][c].costo; if(dist[vecino]>dist[nodo]+costo&&visitado[vecino]==false) { dist[vecino]=dist[nodo]+costo; bdfs(vecino,nodo); } } } void start() { if(dist[F]<INF) cout << dist[F]; else cout << "No solution"; } }; int main() { Grafo g; g.leer(); g.bdfs(g.S,-1); g.start(); cout << endl; return 0; } BFS+DFS Some test, guys? WA 9. Give me some tests, please! I'm repeatedly getting WA in Test#3. I converted all weights to negative and used Bellman-Ford. I also checked if the destination is reachable from the source. Nevertheless, I'm getting WA in the same test case. Could someone give me test case #3? If you use topological sort, and then use dp, you should check that there is a way from s to vertex from which you want to get to the next vertex. My solution is very simple. All weight of edges are inverted((a)->(-a)). Ford-Bellman! Page 1 1) Don't forget, that you have a directed graph! 2) Also don't forget, that standard C++ streams(cin and cout) are very slow! Use scanf and printf. 3) And just use Bellman–Ford algorithm. It works by O(n*m) - in the worst case. Edited by author 08.05.2012 13:16 I have a TL#10, I did Dijkstra's algarithm !!! Tel me please better algarithm than Dijkstra. 0. Use DFS to find all vertices reachable from the start and exclude others from further steps. 1. Use O(m + n) algo. 2. [For C# coders] do not use List or SortedList or even Dictionary! And do not use foreach! 3. Use the fastest input parser you have. For example my parser looks like this: using System; using System.Collections; using System.Collections.Generic; using System.IO; using System.Text; namespace _1450__acm.timus.ru_ { class SerialInput { private static Dictionary<int, int> separators = new Dictionary<int, int> { { ' ', 0 }, { '\n', 0 }, { '\r', 0 } }; private StreamReader reader; public SerialInput(StreamReader reader) { this.reader = reader; } public int ReadInt() { while (separators.ContainsKey(reader.Peek())) reader.Read(); int symbol = reader.Read(); int value = 0; while ((symbol != -1) && !separators.ContainsKey(symbol)) { value = value * 10 + (symbol - '0'); symbol = reader.Read(); } return value; } } class Program { static void Main() { const int InputBufferSize = 65536; const int OutputBufferSize = 65536; #if (ONLINE_JUDGE) var input = new SerialInput( new StreamReader(Console.OpenStandardInput(InputBufferSize))); var output = new StreamWriter(Console.OpenStandardOutput(OutputBufferSize)); #else var input = new SerialInput( new StreamReader(new FileStream(@"..\..\input.txt", FileMode.Open, FileAccess.Read, FileShare.Read, InputBufferSize))); var output = new StreamWriter(new FileStream(@"..\..\output.txt", FileMode.Create, FileAccess.Write, FileShare.Write, OutputBufferSize)); #endif int n = input.ReadInt(), m = input.ReadInt(); // write your code here output.Flush(); } } } I did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance Well, I do not know what this test is, but the answer for this test is "No solution". I don't know how to solve this problem with Dijkstra algorithm. My approach is another. Perhaps one pair of tests below can help you to understand the problem more clearely: 7 7 1 2 10 2 3 10 3 4 5 1 5 1 5 6 50 6 7 50 7 3 50 1 4 ans: 156 7 7 1 2 10 2 3 10 3 4 5 1 5 50 5 6 50 6 7 50 7 3 50 1 4 ans: 205 What you need to do is to find the path with maximum weights of all edges while Dijkstra tries to find minimum. You're solving the wrong problem. Like in the topic can the route of piplines go 2 through the same vertics? That means it goes through and there is a cycle and it returns again through the same vertics and then goes on further The text says "More over, if it is possible to transfer the gas from the station X to the station Y (perhaps, through some intermediate stations), then the reverse transfer from Y to X is impossible." which I think means it can't but I am not sure(?) I would be greatfull for any help, and please no comments - "no comment" better not write at all There is no cycles. So the route can't go twice through the same transfer station. As I thought but I just wanted to be sure Thank you very much Sorry for the offtop, but still... To the situation nowadays, I can only praise my colleagues and myself for the problem statement that remains actual despite three years passed since the contest was held. Long life this problem! :) what answer for this test : 6 7 1 3 5 1 4 10 2 1 5 3 2 5 5 1 1 6 1 2 6 5 2 6 4 13 or 27? thX You have a cycle! 1->3 3->2 2->1 right answer is 28` 6-5-1-3-2-1-4 Read Oleg's comment above... This test is incorrect Try this test: 6 7 6 5 10 1 4 11 1 2 4 3 1 5 2 4 5 6 3 1 6 1 3 5 4 Thanks authors for good problem with funny statement)) Edited by author 23.05.2008 22:10 My program doesn't work on this test. Please, tell me what's wrong with it: #include <stdio.h> int C[500][500],R[500][500],U[500],T[500]; int main(int argc, char* argv[]) { int N,M,start,finish,s,a,b,c,S,F,i,j,u; scanf("%d%d",&N,&M); start=N; s=N-1; for (i=0;i<M;i++) { scanf("%d%d%d",&a,&b,&c); C[a-1][b-1]=c; T[a-1]++; } scanf("%d%d",&S,&F); S--; F--; U[s]=F; for (i=0;i<N;i++) if (i!=S&&i!=F&&T[i]==0) { s--; U[s]=i; } do { finish=start-1; start=s; for (i=finish;i>=start;i--) { b=U[i]; for (j=0;j<N;j++) if (C[j][b]!=0&&j!=S) { T[j]--; if (T[j]==0) { s--; U[s]=j; } } } } while (s<start); U[0]=S; for (i=0;i<N;i++) { a=U[i]; for (j=0;j<N;j++) R[i][j]=C[a][j]; } for (i=0;i<N;i++) { b=U[i]; U[i]=-1; for (j=0;j<N;j++) C[j][i]=R[j][b]; } U[N-1]=0; for (i=N-2;i>=0;i--) { for (j=i+1;j<N;j++) if (C[i][j]!=0&&U[j]!=-1) { u=C[i][j]+U[j]; if (u>U[i]) U[i]=u; } } if (U[0]==-1) printf("No solution"); else printf("%d",U[0]); return 0; } WA6. What's wrong? Give some test's. In my solution I used Deixtra algo. Why Dijkstra? Simple dfs for topsort and then dp. I think this problem could not be solved with dijkstra. Simple dfs for topsort and then dp or simple BFS :) i used FLOYD's algo and have TLE15. i used Djkstra's algo and i have WA10.. pls, can you give me some tests or what's bug in my program? {$APPTYPE CONSOLE} uses SysUtils; var a:array [1..1000,1..1000] of longint; mas:array [1..1000] of longint; used:array [1..1000] of boolean; i,n,m,t,f:longint; procedure djkstra(st:longint); var cur,i:longint; begin fillchar(mas,sizeof(mas),255); fillchar(used,sizeof(used),0); cur:=st; mas[cur]:=0; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and (mas[i]<mas[cur]+a[cur,i]) then mas[i]:=mas[cur]+a[cur,i]; cur:=0; for i:=1 to n do if not used[i] and (mas[i]<>-1)and ((cur=0)or (mas[cur]>mas[i])) then cur:=i; until cur=0; end; begin read(n,m); for i:=1 to m do begin read(t,f); read(a[t,f]); end; read(t,f); djkstra(t); if mas[f]<>-1 then write(mas[f]) else write('No solution'); halt(0); end. and what to do if there is cycle? Edited by author 16.04.2008 21:52 Edited by author 16.04.2008 21:56 Edited by author 16.04.2008 22:55 i've changed djkstra like this <code>procedure djkstra(x:longint); var cur,i:longint; begin fillchar(v,sizeof(v),-1); fillchar(used,sizeof(used),0); v[x]:=0; cur:=x; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and ((v[i]=-1)or (v[i]<v[cur]+a[cur,i])) then begin v[i]:=v[cur]+a[cur,i]; used[i]:=false; end; cur:=0; for i:=1 to n do if not used[i] and (v[i]<>-1)and((cur=0)or (v[cur]<v[i])) then cur:=i; until cur =0; end;</code> and it's tle#15((( I've just noticed, that operators >> and << in C++ STL are very expensive. For this problem operator>> can be called about 124750*3 times. It tooks more than 80% of execution time. I had been improving my solution as much as I can, but always got TLE. With operator>> replaced by scanf it took only 0.078 ms. Somebody.... Anybody... Help I have WA#11 too. Please help me. give me some tests or any hint. Edited by author 23.01.2007 21:09 I have WA#11 too. Please help me. My program works very quickly, but I have time limit. I tested my programm many times. In all test time working is not more than 0,2 sec(even with 500 tops and 124750 edges). Maybe somebody can tell me what is thе 17 test or what is the special trick in this test? Use DP with presorting of course Edited by author 30.09.2006 21:42 It's another problem, where i can TLE troubles with Java. I implemented fastest and correct(!) solution : topological sort + relaxes according to resulting order of vertexes. It works in o(m + n) time, and executing time is very small (0.16 - 0.2 sec) on my computer. I also tried many classes of input/output, but nothing helps. Pls tell me, how can i AC it using Java... OMG, I just wrote this algo using C++, and AC in 0.125. Your java compiler is very bad... maybe you have problems with processing input/output(in java it's too slow) i've used ford-bellman algorithm (0.380 sec) Why i have WA11? I use a wave algo with a queue and edgecency matrix. But there is no mistake. When I wrote a O(m*n) algo it TLE'd on test #16. Your algo is wrong! Use topological sort for solve this problem. Your algo is wrong! Use topological sort to solve this problem. >> Your algo is wrong! >> Use topological sort to solve this problem There is no need in topological sort for this problem, I've got AC with just a simple wave. |
|