CODEWITHSUNDEEP
algorithmdepth-first-searchbreadth-first-search
hack3r
hack3r

Reputation: 573

Unable to find a wrong answer testcase for spoj MMINPAID

Problem link : http://www.spoj.com/problems/MMINPAID/

Getting WA on submitting. I have used bfs to reach Nth node and calculating minimum cost for nodes in a path using bitmask. However after running on a huge number of testcases and comparing with an accepted solution, not able to find a failure testcase. Code:

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 15, INF = 1 << 29;

struct node {
    int c, p, r;
};

struct node data[MAXN][MAXN];
vector<int> g[MAXN];
int N, M, dist[MAXN][1 << 11];

int bfs() {
    for (int i = 0; i < MAXN; i++)
        for (int k = 0; k < (1 << 11); k++) 
            dist[i][k] = INF;
    queue< pair< pair <int, int> , int > > q;
    int v = 1, path = (1 << 1), cost = 0;
    dist[v][path] = 0;
    q.push(make_pair(make_pair(v, path), cost));
    while (!q.empty()) {
        int curv = q.front().first.first;
        int curpath = q.front().first.second;
        int curcost = q.front().second;
        q.pop();

        for (int i = 0; i < g[curv].size(); i++) {
            int nv = g[curv][i];
            int d1 = curcost + data[curv][nv].r;
            int d2 = INF;
            if (curpath & (1 << data[curv][nv].c)) {
                d2 = curcost + data[curv][nv].p;
            }
            int d3 = min(d1, d2);
            int npath = curpath | (1 << nv);
            if (d3 < dist[nv][npath]) {
                dist[nv][npath] = d3;
                q.push(make_pair(make_pair(nv, npath), d3));
            }
        }
    }
    int res = INF;
    for (int i = 0; i < (1 << 11); i++) {
        res = min(res, dist[N][i]);
    }
    return res;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, c, p, r;
        scanf("%d %d %d %d %d", &a, &b, &c, &p, &r);
        g[a].push_back(b);
        data[a][b] = (struct node) {c, p, r};
    }
    int ret = bfs();
    if (ret == INF) printf("impossible\n");
    else printf("%d\n", ret);

    return 0;
}

Upvotes: 0

Views: 166

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

I think the problem might be that your data[a][b] structure assumes there is at most a single road from a to b.

However, the problem states:

There may be more than one road connecting one city with another.

Upvotes: 3

Related Questions