#P18596. Shortest Path Query
Shortest Path Query
Shortest Path Query
给定一张有向无环图,顶点编号为 。每条边有黑、白两种颜色之一,且从顶点 可以到达所有顶点。
你需要独立回答 个询问。一个询问给出 :在这次询问中,把每条黑边的长度设为 ,每条白边的长度设为 ,求从 到 的最短路径长度。询问不会永久修改图,也不影响其他询问。
输入格式
第一行给出两个整数 ,表示顶点数和有向边数。
接下来 行,每行三个整数 ,描述一条从 指向 的边。 表示黑边, 表示白边。
接下来一行给出整数 。
接下来 行,每行三个整数 ,表示一个询问。
数据满足:
- ,;
- ,,;
- 从顶点 可以到达每个顶点;
- ;
- ,。
输入只有一组图,不含测试组数 。边在输入中的先后顺序没有额外限制。
输出格式
按输入顺序输出 行,每行一个整数,为对应询问的最短路径长度。当 时,空路径的长度为 。
样例输入 1
4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4
样例输出 1
3
4
4
样例说明
到顶点 有一条由两条黑边构成的路径,以及一条由两条白边构成的路径。后两个询问分别选择全白和全黑路径,长度都为 。