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 did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance

#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.

Somebody.... Anybody... Help

My solution is very simple. All weight of edges are inverted((a)->(-a)). Ford-Bellman!

Give me this test plz

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

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

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?

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.

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;
}