Näitelahendused, Graafid 2

229B.py

from heapq import *
from collections import defaultdict
from sys import stdin

def readNums():
    return [int(x) for x in stdin.readline().split()]

planets, no_roads = readNums()
# if we do roads[key].append(value) and key wasn't set before, we get roads[key] == [value]
# avoids doing 
# if key in roads: roads[key].append(value) 
# else: roads[key] = [value]
roads = defaultdict(list)
for _ in range(no_roads):
    a, b, cost = readNums()
    roads[a-1].append((b-1, cost))
    roads[b-1].append((a-1, cost))
waittimes = []
for _ in range(planets):
    times = readNums()
    waittimes.append(set(times[1:]))

def dijkstra(planets, roads, waittimes):
    " Returns an list containing the distances of cities from source "
    # assume cities are numbered [0..cities-1]
    times = [10**10] * planets # at the beginning, mark distances as infinity
    times[0] = 0
    heap = [(0, 0)] # time as first element, planet as second
    while len(heap) > 0:
        time, planet = heappop(heap) # remove the element with smallest time
        #print time, planet
        if time > times[planet]: continue # skip, we were here faster before
        while time in waittimes[planet]: # travellers arriving
            time += 1
        for nextPlanet, cost in roads[planet]:
            if times[nextPlanet] > time + cost: # if we get there faster this way
                times[nextPlanet] = time + cost
                heappush(heap, (time + cost, nextPlanet)) # next place to the heap
    return times
     
times = dijkstra(planets, roads, waittimes)
if times[planets-1] < 10**10:
    print times[planets-1]
else:
    print -1

295B.cpp

#include <iostream>
using namespace std;
#define MAXN 512
#define min(a, b) ((a) < (b) ? (a) : (b))

int size;
long long distances[MAXN][MAXN];
int removeOrder[MAXN];
long long results[MAXN];

long long matrixSum(int at) {
    long long result = 0, i, j;
    for (i = 0; i <= at; i++) {
        for (j = 0; j <= at; j++) {
            result += distances[removeOrder[i]][removeOrder[j]];
        }
    }
    return result;
}

int main() {
    int a, b, via;

    cin >> size;
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            cin >> distances[i][j];


    for (int i = 0; i < size; i++) {
        cin >> a;
        removeOrder[size-i-1] = a-1;
    }

    for (int i = 0; i < size; i++) {
        via = removeOrder[i];
        for (a = 0; a < size; a++) {
            for (b = 0; b < size; b++) {
                distances[a][b] = min(
                    distances[a][b],
                    distances[a][via] + distances[via][b]);
            }
        }
        results[i] = matrixSum(i);
    }
    for (int i = size-1; i >= 0; i--) {
        cout << results[i];
        if (i == 0) cout << '\n';
        else cout << ' ';
    }

    return 0;
}

295B.py

# http://codeforces.com/problemset/problem/295/B

from collections import defaultdict, deque
from sys import stdin

def readNums(single=False):
    if single:
        return int(stdin.readline())
    return [int(x) for x in stdin.readline().split()]

size = readNums(True)
distances = [readNums() for _ in range(size)]
removeOrder = readNums()

def matrixSum(matrix, rows):
    result = 0
    for i in rows:
        for j in rows:
            result += matrix[i][j]
    return result

# Run floyd warshall in reverse
results = []
rows_processed = set()

for via in reversed(removeOrder):
    via -= 1
    for a in xrange(size):
        for b in xrange(size):
            distances[a][b] = min(distances[a][b], distances[a][via] + distances[via][b])

    rows_processed.add(via)
    summ = matrixSum(distances, rows_processed)
    results.append(str(summ))

print ' '.join(reversed(results))

95C.py

# http://codeforces.com/problemset/problem/95/C

from collections import defaultdict
from heapq import *
from sys import stdin

def readNums(single=False):
    if single:
        return int(stdin.readline())
    return [int(x) for x in stdin.readline().split()]

junctions, roads = readNums()
start, end = readNums()

neighbors = defaultdict(list)
drivers = {}
for _ in xrange(roads):
    a, b, cost = readNums()
    neighbors[a].append((b, cost))
    neighbors[b].append((a, cost))
for i in xrange(1, junctions+1):
    drivers[i] = readNums() # distance, cost

def shouldGo(node, cost, fuel, costs, maxFuel):
    prevCost = costs.get(node, float('inf'))
    prevFuel = maxFuel.get(node, -1)
    # If been going there is objectively worse, skip
    if cost >= prevCost and fuel <= prevFuel:
        return False
    return True

def dijkstra(start, end):
    costs = {start: 0}
    maxFuel = {start: 0}
    heap = [(0, start, 0, False)] # (moneySpent, position, taxiTimeLeft)
    while len(heap) > 0:
        # print heap
        moneySpent, position, fuelLeft, hadCabbie = heappop(heap)
        # print moneySpent, position, fuelLeft, costs[position], maxFuel[position]
        if position == end:
            return moneySpent
        # option A: switch cabbie
        driverDistance, driverCost = drivers[position]
        if fuelLeft != driverDistance and not hadCabbie:
            heappush(heap, (moneySpent + driverCost, position, driverDistance, True))
        # option B: continue driving
        for node, distance in neighbors[position]:
            next_fuel = fuelLeft - distance
            # print "  ", node, distance, next_fuel
            if next_fuel >= 0 and shouldGo(node, moneySpent, next_fuel, costs, maxFuel):
                costs[node] = moneySpent
                maxFuel[node] = next_fuel
                heappush(heap, (moneySpent, node, next_fuel, False))
    return -1

print dijkstra(start, end)