Linked Questions

Popular Questions

Get wrong answer for spoj MMINPAID

Asked by At

here is my source code,and the main idea list as below: 1.I use bfs to tranverse the graph,the graph is saved in a vector array 2.I use bitmask to record the city has travel, if the bitmask contain the city ci, then use P, else use R 3.I use a priority_queue sorted by cost,each time take the min cost element However I always get WA on test case 8,can anyone help me where I do wrong

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 10243
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
 ((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }

const int MAX_INT = 1e9 + 1;
const long long inf = 1e18;
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};



#define N 105


int T = 1;
int n, m, k;

int dis[11][1<<11];

struct node {
    int b, c, P, R;

    node(int city, int mcity, int w1, int w2) : b(city), c(mcity), P(w1), R(w2) {}
};

vector<node> maze[11];

struct elem {
    int city, mask, cost;

    elem(int city, int mask, int w) : city(city), mask(mask), cost(w) {}
};

struct cmp {
    bool operator() (const elem &p1, const elem &p2) {
        return p1.cost > p2.cost;
    }
};

int bfs() {
    priority_queue<elem, vector<elem>, cmp> que;
    int ans = INF;
    m_init(dis, INF);
    dis[1][2] = 0;
    que.emplace(1, 2, 0);
    while (!que.empty()) {
        auto state = que.top();
        que.pop();
        for(auto &&e : maze[state.city]) {
            int cost = state.cost;
            if (state.mask & (1<<e.c)) {
                cost += e.P;
            }
            else {
                cost += e.R;
            }
            int mmsk = state.mask | (1<<e.b);
            if (cost < dis[e.b][mmsk]) {
                dis[e.b][mmsk] = cost;
                if(e.b == n) {
                    Min(ans, dis[e.b][mmsk]);
                }
                que.emplace(e.b, mmsk, dis[e.b][mmsk]);
            }
        }
    }
    return ans;
}



int main()
{
    srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
//    scanf("%d", &T);
//    C_init();
//    while (T--)
    while (~scanf("%d%d", &n, &m))
//    repi(c,1,T+1)
    {
        int a,b,c,p,r;
        repi(i,0,m){
            scanf("%d%d%d%d%d", &a, &b, &c, &p, &r);
            maze[a].eb(b,c,p,r);
        }
        int ans = bfs();
        if(ans == INF) {
            puts("impossible");
        }
        else {
            printf("%d\n", ans);
        }

    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

Related Questions