DoubleWeights
SRM 685 · 2016-03-02 · by cgy4ever
SRM 685 · 2016-03-02 · by cgy4ever · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
We have a simple undirected graph G with n nodes, labeled 0 through n-1.
Each edge of this graph has two weights.
You are given the description of G encoded into String[] s weight1 and weight2.
If nodes i and j are connected by an edge, both weight1[i][j] and weight2[i][j] are nonzero digits ('1'-'9'), and these represent the two weights of this edge.
Otherwise, both weight1[i][j] and weight2[i][j] are periods ('.').
Your task is to find the cheapest path from node 0 to node 1. The cost of a path is calculated as (W1 * W2), where W1 is the sum of all first weights and W2 is the sum of all second weights of the edges on your path. Return the smallest possible cost of a path from node 0 to node 1. If there is no such path, return -1 instead.
Your task is to find the cheapest path from node 0 to node 1. The cost of a path is calculated as (W1 * W2), where W1 is the sum of all first weights and W2 is the sum of all second weights of the edges on your path. Return the smallest possible cost of a path from node 0 to node 1. If there is no such path, return -1 instead.
Constraints
- n will be between 2 and 20, inclusive.
- weight1 and weight2 will contain exactly n elements, each.
- Each element in weight1 and weight2 will contain exactly n characters.
- Each character in weight1 and weight2 will be '.' or '1' - '9'.
- For each i, weight1[i][i] = weight2[i][i] = '.'.
- For each i and j, weight1[i][j] = weight1[j][i].
- For each i and j, weight2[i][j] = weight2[j][i].
- weight1[i][j] = '.' if and only if weight2[i][j] = '.'.
Examples
0)
{"..14",
"..94",
"19..",
"44.."}
{"..94",
"..14",
"91..",
"44.."}
Returns: 64
The best path is 0 -> 3 -> 1. The cost of this path is (4+4) * (4+4) = 64. Note that the other possible path (0 -> 2 -> 1) is more expensive. Its cost is (1+9) * (9+1) = 100.
1)
{"..14",
"..14",
"11..",
"44.."}
{"..94",
"..94",
"99..",
"44.."}
Returns: 36
This time the best path is 0->2->1, the cost is (1+1) * (9+9) = 36.
2)
{"..",
".."}
{"..",
".."}
Returns: -1
There is no path between node 0 and node 1, so you should return -1.
3)
{".....9",
"..9...",
".9.9..",
"..9.9.",
"...9.9",
"9...9."}
{".....9",
"..9...",
".9.9..",
"..9.9.",
"...9.9",
"9...9."}
Returns: 2025
4)
{".4...1",
"4.1...",
".1.1..",
"..1.1.",
"...1.1",
"1...1."}
{".4...1",
"4.1...",
".1.1..",
"..1.1.",
"...1.1",
"1...1."}
Returns: 16
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DoubleWeights with a public method int minimalCost(vector<string> weight1, vector<string> weight2) · 66 test cases · 2 s / 256 MB per case