爱悠闲 > hdu5422(BC)

hdu5422(BC)

分类: c/c++  |  标签: 水  |  作者: d_x_d 相关  |  发布日期 : 2015-08-26  |  热度 : 255°

链接:http://acm.hdu.edu.cn/showproblem.php?pid=5422


There are no more than 100 testcases.

For each testcase, the first line contains two numbers n,m(2n100,0m100) .

Then m lines follow. Each line contains two numbers u,v(1u,vn) , which means there is an edge between u and v . There may be multiedges and self loops.

Output
For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice n and the number of the ways of adding this edge.

Sample Input
  
  
2 1 1 2

Sample Output
  
  
1 1
Hint
You can only add an edge between 1 and 2.

Source

只要注意是无向图就OK


#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;

int n,m;
int mat[105][105];

int main ()
{
    int a,b,flag;
    while (scanf ("%d%d",&n,&m)==2)
    {
        flag=0;
        memset(mat, 0, sizeof(mat));
        for (int i=0; i<m; i++)
        {
            scanf ("%d%d",&a,&b);
            if ((a==1&&b==n)||(a==n&&b==1))
                flag=1;
            if (a!=b&&!mat[a][b])
            {
                mat[a][b] = 1;
                mat[b][a] = 1;
            }
        }
        if (!flag)
            printf ("1 1\n");
        else
            printf ("1 %d\n",n*(n-1)/2);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。