• [A] radical's want to eat dinner

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • As you know, radical is a pupil who likes to play a game lal. So after school, he always go to an internet bar near his school and play lal before the dinner begin. And then, a problem comes to him.
    radical lives in a town, where every place can be regard a point, and some of them can be connected by some bidirection roads with length. Every time when radical realize that he need to go home to eat dinner, he will be confused, for he dose not know how to get home as quickly as possible. So he call his dad zxxxz for help. But zxxxz is busy cooking dinner for his son, so he sometimes just casually tell radical some roads. If radical walk along these roads, he will get home as quickly as possible. But radical doubts the way his dad gives him, so he asks you for help: is it the shortest way from internet bar to his house?
  • 输入
  • The first line: two integers n, m (1 <= n <= 1000, n <= m <= n^2), m is the total number of the roads and n is the total number of places in the town.1 is the house of radical, and n is the internet bar where he plays in.
    The follow m lines contain four integers u, v, w, f ( 1 <= u, v <= n, u != v, 1 <= w <= 1000, 0 <= f <= 1 ). There is a way from u to v, and the length of the way is w. And if f is 1 means that the road from u to v is one of the roads of which radical's dad tells him. It's guaranteed that the sum of all roads f is n-1.
  • 输出
  • For each case, output "Yes" if radical's dad tell him the shortest way, or "No" if radical's dad didn't.
  • 样例输入
  • 3 3
    1 2 1 1
    2 3 1 1
    1 3 2 0
  • 样例输出
  • Yes
  • 提示
  • 来源
  • 本站或者转载
  • 操作