aajjbb's blog

By aajjbb, 11 years ago, In English

Hello, I'm trying to solve the problem Tax;

In a first glance, it looks like a little modified Dijksta algorithm, using the weight as the max value of the last weight edge weight and the current weight, like the code I did here.

But unfortunately this idea only work for 3 test cases, can you point what is wrong with this code, or the right idea for tackle this problem ?

Thanks in advance.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <memory>
#include <iomanip>
#include <numeric>
#include <functional>
#include <new>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cctype>
#include <ctime>

#define REP(i, n) for(int (i) = 0; i < n; i++)
#define FOR(i, a, n) for(int (i) = a; i < n; i++)
#define FORR(i, a, n) for(int (i) = a; i <= n; i++)
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
#define sz(n) n.size()
#define pb(n) push_back(n)
#define all(n) n.begin(), n.end()

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INF = 1000010100980980LL;
const int MAXN = 100009;
int N, M, a, b, c;
vector<pair<int, int> > graph[MAXN];
ll dist[MAXN];

ll func(int hashiri, int saigo) {
    for(int i = 0; i <= N; i++) dist[i] = INF;

    dist[hashiri] = 0LL;
    priority_queue<pair<int, int> > q;

    //Last bigger, index;
    q.push(make_pair(0, hashiri));

    while(!q.empty()) {
        int last = q.top().first, index = q.top().second; q.pop();

        for(int i = 0; i < graph[index].size(); i++) {
            int next = graph[index][i].first, cost = graph[index][i].second;
            int real_cost = max(cost, last);

            if(next == saigo) real_cost += cost;

            if(dist[index] + real_cost < dist[next]) {
                dist[next] = dist[index] + real_cost;
                q.push(make_pair(cost, next));
                printf("%d %d\n", index, next);
            }
        }
    }

    return dist[saigo];
}

int main(void) {
    scanf("%d%d", &N, &M);

    REP(i, M) {
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    printf("%lld\n", func(1, N));

    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Your solution is wrong because there can exist two different path into one vertex but with different costs of last edges.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I'm using the pair structure to store the cost of the previous node for each next node, so I always use the cost for the right last node.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok. first path cost is 10, cost of last edge is 5, cost of second path is 11, but cost of last edge is 1. there can be situation when it is better to use second path, but your program will not consider it.

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I think I fixed it duplicating the cost of all edges ending on vertex 'N', but there are yet WA and some cases, infinite loops.