Words, Graphs and Edges
Practice
3.7 (3 votes)
Mathematics
Graph
Matrix exponentiation
Medium Hard
Linear algebra
Problem
94% Success 2082 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

A complex cryptosystem works as follows:

You have n words and if you put a vertex for any word in the graph, then you will use some edges between them and color each one of them

In this system, a key is defined as follows:

(c1,c2,...,c|c|)*k which means that the order(c1,c2,...,c|c|) repeats k times

For example, the key (1,2)*3 =(1,2,1,2,1,2) (1 and 2 are colors) or the key (3,8,1)*2 = (3,8,1,3,8,1).

So, a color can repeat multiple times as shown in the example.

In order to use two words instead of each other, the set of paths between them must be in the following order:

Note: In a path, a vertex and an edge can be repeated multiple times.

1. The edges in the path must be exactly like the key.

2. The number of paths with the given condition must be greater than or equal p (for security).

You are given a graph with colored edges, key, two vertices, and p.

You need to find out if there is a set of paths that follows the order between those two vertexes.

Input format

  • First line: Six integers n,m,p,|c|,u,v (1<=n<=100 , 1<=u,v<=n , 1<=m<=n*(n-1)/2, 1<=p<=100 , 1<=|c|<=20)
    • n is number of words
    • m is the number of edges(in-built graph)
    • p is defined in the second order 
    • u and v show the 2 words used instead of each other
  • Second line: |c| integer representing the key colors and an integer k representing the number of reputation (1<=ci<=20 , 1<=k<=1000000),
  • Each of the last m lines: 3 integers x,y, and w indicating that there is an edge between x and y with the color w(1<=x, y< =n, 1<=w<=20).

Output format

    Print YES, if there is a set of paths and NO otherwise.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
1 votes
Tags:
Linear AlgebraMatrix ExponentiationMedium-HardMathematics