Internet Router Congestion

Hard

graph directed-graph packet-flow threshold-checking

Problem Description

Given a directed graph of routers and packet counts flowing through them, find which router will fail first when it exceeds its overload threshold.

Input Format

First line: n m (routers, connections). Next m lines: from to packets. Next line: n thresholds for routers.

Output Format

Router ID that fails first, or -1 if no router fails.

Constraints

• 1 ≤ n ≤ 1000

• 0 ≤ m ≤ 5000

• 1 ≤ packet counts ≤ 1000

• 1 ≤ thresholds ≤ 10000

• Routers numbered 1 to n

• Router fails when total incoming packets > threshold

Sample Input/Output

Input:

3 4
1 2 100
1 3 200
2 3 150
3 1 50
300 400 300

Output:

Explanation

Router 3 receives 200+150=350 packets, exceeding threshold 300. Other routers are within limits.

Solution Hints

145
Points

3000ms
Time Limit

256MB
Memory Limit

Code Editor

Register to Access Code Editor

Create a free account to solve coding problems and track your progress.