There is a country named [Сensored]. In this country the national instrument is called "balalayka". In the capital of [Сensored] the biggest square is called Red Square... I don't have nothing against [Сensored], but there are some idiots who live there (like Gyrinovskiy), that like to say before think! And what thay say is very politically uncorrect! I hope that authors of the problem are not such idiots. I'd like to wish the authors of the problem to think more before write such things in the problem statement. It would be very nice for you to change the problem statement completly. best regards, Ostap Korkuna. I want to propose you to make your own contest  and I will be really pleased to read another funny story about country named [Censored] ;) Anyway, the task statement offends me in particular and I belive that there are a lot of other respected people, who are offended by such kind of "jokes". In my opinion this "joke" has overstepped the limits of innocents... See, one may feel offended even if I write "the sky is blue". No concrete names of people and country are mentioned. Why do you think the story is about your country I respect very much? There are a lot of countries in the world who deal with Russian gas. Not all of them steal it in fact ;) But if you associate [Censored] with you country  you must have some reasons... More people from your country will complain about this problem  more people may think something politically incorrect about it. But we are not guilty of it, aren't we? Relax, the story is really cool. Maybe next time we will write something funny about the presidential elections in [Censored] ;))) Edited by author 24.04.2006 23:58 Dmitry, it seems that Michael Rybak is not the only man offended by this task statement. Isn't it? As the administrator of this site I DEMAND this task statement to be rewritten. It DOES offend visitors of this site regardless of which coutry is hidden under phrase '[Censored]'. Otherwise you have a choice: either I will change task statement by myself or task will be hidden from public (or completely removed from archive). Everybody who got offended by the statement of this task, let me know about it in this thread. I completely agree with you. Please, avoid offending messages. Just let me know that there are a lot of people who wants Timus to be over politics. And let me know, which solution would you prefer: change of statement or task removal. as Russian citizen i think that shuld corect not only tsk about [cenzored] country but and 1457(about old pop), and ALL task in timus archive wich creat wrong understending about my GREAT matherland :) First, if the statement will be changed by you, all our twenty problems will be locked until we may come to some decision. And lots of programmers who have sense of humour and want to solve these problems will thank you very much for what you achieved because of several malcontents. Second, now Ilya Grebnov, Nikita Rybak and me are trying to think out something. We need at least one day to do it. Third, if you think it is so just and noble of you to put pressure upon us, you are mistaken. You forget something. We are not your subordinates. You do not pay us money for what we are doing here  for the sake of Timus Online Judge by the way. As you could see, our contests are much more popular than any contests before. We are still the Top Coders. So try to learn to respect us  at least as this site's best programmers  OK? P.S. Now we are working at "Pascal vs. C++. Version 2" problem which is going to be added to the Volume 4 soon. But because of you we had to slow down our activity. Thank you very much, it is very useful for Timus. ============================================================ IBM is short, Pascal is forever! Edited by author 25.04.2006 03:04 Our, i'm so impressed by you kindness, really , yes you won't get paid for changing problem statement, but i'd like to inform you that in civilized world there exists such thing as "law" and your problem can be recognized as offending honour of some country and peoople, so try be more carefull in future plz. Of course i understand that changing problem statement is a really exhausting job, so thank you for this great effort! No one wants to put pressure on you! We just want to make problem statements nonpolitical and inoffensive. You may assume it as a basic rules of this site. JOKE? Where is a joke? Your Country repeatedly do it. And every time your Goverment with the disgrace plead guilty. You may call it "technical selection of gas" but we call a spade a spade. Goverment plead guilty and I don't understand why you think that the statement is pollitically incorect. We know that our geverment nothing better. And we say about it, for example, in the statement of problem # 1457 Edited by author 17.06.2006 16:44 respect to authors. others can kill themselves by hitting the wall. Can anybody upload original statement? Школота detected. Such an intellectual "humor" from authors. It was kind of surprise to find such shet on Timus. Edited by author 02.12.2019 12:02 Edited by author 02.12.2019 12:02 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. #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 BellmanFord. 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. 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 solution is very simple. All weight of edges are inverted((a)>(a)). FordBellman! I have a TL#10, I did Dijkstra's algarithm !!! Tel me please better algarithm than Dijkstra. 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 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` 6513214 Read Oleg's comment above... This test is incorrect 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(); } } } 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 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 fordbellman algorithm (0.380 sec) 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! :) 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((( 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=N1; for (i=0;i<M;i++) { scanf("%d%d%d",&a,&b,&c); C[a1][b1]=c; T[a1]++; } 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=start1; 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[N1]=0; for (i=N2;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; } Sorry, I got AC. Haven't noticed a slight trick. Well, it's a DAG. Therefore you can simply use DFS, that's all. What trick???? I have WA 10 too....... Could anybody give me a test to solve this problem? My program works correctly whith MY tests and whith the first 9 timus tests)... Why you trying to razvesti us? It's not a DFS, it's Deykstra algo or maybe FloidWarshal Lol. So, try to solve problem with your algo especially for N<=500. 
