Easy sssp
【描述】
输入数据给出一个有N(2 <= N <= 1,000)个节点,M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
【格式】
【输入格式】
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)
【输出格式】
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出“NoPath”;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度.
Sample 1
Input
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4
Output
0
6
4
-3
-2
7
Limitation
1s, 256MiB for each test case.
Test5 5秒
其余 1秒
Hint
Free Pascal Code
var a,b:longint;
begin
readln(a,b);
writeln(a+b);
end.
C Code
#include <stdio.h>
int main(void)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
return 0;
}
C++ Code
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a + b << endl;
return 0;
}
Python Code
a, b = [int(i) for i in raw_input().split()]
print(a + b)
Java Code
import java.io.*;
import java.util.Scanner;
public class Main {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(a + b);
}
}
Source
Vijos Original
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 11
- 已通过
- 2
- 通过率
- 18%
- 上传者