1247 - Interstar Transport

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 1247 - Interstar Transport

Post by nbacool2 » Tue Jan 20, 2015 12:39 am

Any ideas why I'm getting WA? I'm using Floyd-Warshall's All pairs shortest paths algorithm in addition to making backtracking on the local optimal parameters

Code: Select all

#include <iostream>
#include <cstring>
#include <iomanip>
#include <vector>
#include <utility>
using namespace std;
typedef pair<char, char> ii;
const int INF = 1 << 27;
const int MAXS = 30;
int S, P;
int graph[MAXS][MAXS];
int b[MAXS][MAXS];
int l[MAXS][MAXS];
vector<ii> queries;

void read()
{
    queries.clear();
    memset(b, -1, sizeof b);
    memset(l, 0, sizeof l);
    for(int i = 0; i < MAXS; ++i)
    {
        for(int j = 0; j < MAXS; ++j)
        {
            graph[i][j] = INF;
        }
        graph[i][i] = 0;
    }
    for(int i = 0; i < P; ++i)
    {
        char a, b;
        int d;
        cin >> a >> b >> d;
        graph[a - 'A'][b - 'A'] = d;
        graph[b - 'A'][a - 'A'] = d;
    }
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i)
    {
        char from, to;
        cin >> from >> to;
        queries.push_back(ii(from, to));
    }
}
void Floyd_Warshall()
{
    for(int k = 0; k < MAXS; ++k)
    {
        for(int i = 0; i < MAXS; ++i)
        {
            for(int j = 0; j < MAXS; ++j)
            {
                if(i == j || i == k || j == k) continue;
                if(graph[i][k] + graph[k][j] < graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    b[i][j] = k;
                    l[i][j] = l[i][k] + l[k][j] + 1;
                }
                else if(graph[i][k] + graph[k][j] == graph[i][j] && l[i][k] + l[k][j] + 1 < l[i][j])
                {
                    l[i][j] = l[i][k] + l[k][j] + 1;
                    b[i][j] = k;
                }
            }
        }
    }
}
void backtrack(int from, int to)
{
    int intermidiate = b[from][to];
    if(intermidiate == -1) return;
    backtrack(from, intermidiate);
    cout<<' '<<(char)(intermidiate + 'A');
}
void solve()
{
    Floyd_Warshall();
    for(int i = 0; i < queries.size(); ++i)
    {
        cout<<queries[i].first;
        backtrack(queries[i].first - 'A', queries[i].second - 'A');
        cout<<' '<<queries[i].second;
        cout<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin >> S)
    {
        cin >> P;
        read();
        solve();
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1247 - Interstar Transport

Post by brianfry713 » Thu Jan 22, 2015 12:08 am

Try solving it with Dijkstra's algorithm.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 12 (1200-1299)”