Category Archives: Dijkstra

(LightOj) 1281 – New Traffic System

0
Posted on by 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here

#define MAXX 10003

struct graphNode{
    int weight;
    int v;
    bool isProposedRoad;
};
struct node{
    int cost;
    int used;
    int u;

    bool operator<(const node &ob) const
    {
        return this->cost > ob.cost;
    }
};



vector<graphNode>graph[MAXX];
int n, m, k, d;
int dist[11][MAXX];



int dijkstra()
{
    //cerr<<endl;
    node u, v;
    u.u = u.cost = u.used = 0;

    mem(dist, 1);
    dist[0][0] = 0;


    priority_queue<node>Q;
    Q.push(u);


    while(!Q.empty())
    {
        u = Q.top(); Q.pop();
        //cerr<<"dist["<<u.u<<"]["<<u.used<<"] = "<<u.cost<<endl;
        if(u.cost != dist[u.used][u.u]) continue;
        if(u.u == n-1)
        {
            //dump(u.cost);
            return u.cost;
        }

        loop(i, SZ(graph[u.u]))
        {
            //cerr<<u.u<<" -->"<<graph[u.u][i].v<<endl;
            v.u = graph[u.u][i].v;
            v.cost = graph[u.u][i].weight + u.cost;
            v.used = u.used + (graph[u.u][i].isProposedRoad?1:0);


            if(v.used <= d && v.cost < dist[v.used][v.u] )
            {
                dist[v.used][v.u] = v.cost;
                Q.push(v);
                //cerr<<"pushing "<<v.u<<" with cost "<<v.cost<<endl;
            }
        }
    }

    return -1;
}




int main()
{
    int kases, kaseno = 0;

    take(kases);

    while(kases--)
    {



        graphNode aNode;
        take(n, m, k, d);


        loop(i, n) graph[i].clear();

        int u, v, w;
        aNode.isProposedRoad = false;
        loop(i, m)
        {
            take(u, v, w);
            aNode.weight = w;
            aNode.v = v;
            graph[u].pb(aNode);
        }

        aNode.isProposedRoad = true;

        loop(i, k)
        {
            take(u, v, w);
            aNode.weight = w;
            aNode.v = v;
            graph[u].pb(aNode);
        }

        int res = dijkstra();
        if(res == -1) pf("Case %d: Impossible\n", ++kaseno);
        else pf("Case %d: %d\n", ++kaseno, res);


    }



}

(USACO) Sweet Butter

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=wgELNYzwxkD&amp;S=butter

/*
ID: himuhas1
TASK: butter
LANG: C++
*/
/*
ID: himuhas1
TASK: butter
LANG: C++
*/



#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here
int N, P, C;

#define MAXP 802

int cntCows[MAXP];
ll dist[MAXP];
vector<paii>paths[MAXP];
bool visited[MAXP];

struct comp{
    bool operator()(paii a, paii b)
    {
        return a.fr > b.fr;
    }
};

void bfs(paii u)
{
    int _cost[MAXP];
    mem(_cost, 127);
    mem(visited, 0);

    paii v;

    priority_queue<paii, vector<paii>, comp>Q;
    Q.push(u);
    _cost[u.sc] = 0;
    int mul = cntCows[u.sc];
    //visited[u.sc] = 1;

    while(!Q.empty())
    {
        u = Q.top();

        Q.pop();
        if(!visited[u.sc])
        {
            visited[u.sc] = 1;
            dist[u.sc] += (_cost[u.sc]*mul);  //here to modify
            loop(i, SZ(paths[u.sc]))
            {
                v.sc = paths[u.sc][i].fr;
                if(!visited[v.sc] && _cost[u.sc]+paths[u.sc][i].sc < _cost[v.sc])
                {
                    //dump(i);
                    _cost[v.sc] = _cost[u.sc]+paths[u.sc][i].sc;
                    v.fr = _cost[v.sc];
                    //dump(v.sc);
                    //dump(v.fr);


                    Q.push(v);
                }
            }
        }
    }
}


int main()
{
    #ifndef hasibpc
        read("butter.in");
        write("butter.out");
    #endif

    take(N, P, C);
    int a,b,cost;

    loop(i, N)
    {
        take(a);
        cntCows[a]++;
    }

    loop(i, C)
    {
        take(a, b, cost);
        paths[a].pb(MP(b, cost));
        paths[b].pb(MP(a, cost));
    }

    for(int i=1; i<=P; i++)
    {
        if(cntCows[i])
        {
            bfs(MP(0, i));
        }
    }

    ll result = 1<<29;

    for(int i=1; i<=P; i++)
    {
        //dump(dist[i]);
        result = min(result, dist[i]);
    }

    cout<<result<<endl;







    return 0;
}

Bessie Come Home (USACO)

0
Posted on by 
/*
ID: himuhas1
TASK: comehome
LANG: C++
*/



#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define dump(x) cout<<#x<<" = "<<(int)x<<endl
#define INF (1<<29)

using namespace std;

#define MAXX 52

vector<paii> graph[MAXX];


void toInt(char &c)
{
    if('A' <= c && c <= 'Z')
        c = c -'A' + 26;
    else
        c = c - 'a';
}

struct DATA{
    char idx;
    int d;
    bool operator<(const DATA& a) const
    {
        return d > a.d;
    }
};

int dist[MAXX];

void dijkstra()
{
    paii result;
    result.sc = INF;
    priority_queue<DATA>Q;
    loop(i, MAXX) dist[i] = INF;
    dist[51] = 0;
    DATA u,v;
    u.idx = 51;
    u.d = 0;
    Q.push(u);

    while(!Q.empty())
    {
        u = Q.top(); Q.pop();
        //dump(u.idx);
        if(u.d && u.idx > 25 && u.d < result.sc)
        {
            result.fr = u.idx;
            result.sc = u.d;
        }

        if(dist[u.idx] == u.d)
        {
            loop(i, SZ(graph[u.idx]))
            {
                v.idx = graph[u.idx][i].fr;
                //cout<<"\t"; dump(v.idx);
                v.d = u.d + graph[u.idx][i].sc;
                if(dist[v.idx] > v.d )
                {
                    dist[v.idx] = v.d;
                    Q.push(v);
                }
            }
        }
    }

    result.fr = result.fr - 26 + 'A';
    cout<<(char)result.fr<<" "<<result.sc<<endl;


}

int main()
{
    #ifndef hasibpc
        freopen("comehome.in", "r", stdin);
        freopen("comehome.out", "w", stdout);
    #endif // hasipc
    int paths;
    gi(paths);
    char a, b;
    int d;

    loop(i, paths)
    {
        cin.ignore();
        sf("%c %c %d", &a, &b, &d);
        //dump(a); dump(b); dump(d);
        toInt(a);
        toInt(b);
        //dump(a); dump(b);
        graph[a].pb(MP(b,d));
        graph[b].pb(MP(a,d));
    }

    dijkstra();





    return 0;
}

(lightOj) 1002 – Country Roads

0
Posted on by 
/*
user: php
time: 0.276 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1002
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<vector>
#include<queue>

#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define SZ size()
#define mem(ara, val) memset(ara, val, sizeof(ara))
#define pi acos(-1.0)
#define INF 1<<29
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define pb push_back
#define ll long long
#define geti(n) scanf("%d",&n)
#define MAXX 505



using namespace std;


int weight[MAXX][MAXX];


vector<int>node[MAXX];

int dist[MAXX];

struct DATA{
    int city, dist;
};

struct compare{
    bool operator()(DATA a, DATA b)
    {
        return a.dist > b.dist;
    }

};


void dijkstra(int source)
{
    int len;
    priority_queue<DATA, vector<DATA>, compare >Q;
    DATA u, v;
    u.city = source;
    u.dist = 0;

    dist = 0;

    Q.push(u);
    while( !Q.empty() )
    {
        u = Q.top(); Q.pop();

        if(u.dist != dist[u.city]) continue;

        len = node[u.city].SZ;

        loop(i, len)
        {
            v.city = node[u.city][i];
            v.dist = max(u.dist, weight[u.city][v.city]);
            if(v.dist < dist[v.city])
            {
                dist[v.city] = v.dist;
                Q.push(v);
            }
        }

    }
}




int main()
{
    int kases, kaseno = 0;
    int cities, roads;
    geti(kases);
    int p, q, w;
    int source;

    while(kases--)
    {
        loop(i, MAXX)
        {
            node[i].clear();
            dist[i] = INF;
            loop(j, MAXX)
            {
                weight[i][j] = INF;
                weight[j][i] = INF;
            }
        }


        geti(cities);
        geti(roads);
        loop(i, roads)
        {
            geti(p); geti(q); geti(w);
            if(w < weight[p][q])
            {
                weight[p][q] = w;
                weight[q][p] = w;
                node[p].pb(q);
                node[q].pb(p);
            }
        }

        geti(source);
        dijkstra(source);

        printf("Case %d:\n", ++kaseno);



        loop(i, cities)
        {
            if(dist[i] == INF)
                printf("Impossible\n");
            else
                printf("%d\n", dist[i]);
        }



    }



    return 0;
}