文章出處

Rikka with Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 182 Accepted Submission(s): 95

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with

Input

There are no more than 100 testcases.
For each testcase, the first line contains two numbers

Output

For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice

Sample Input

2 1

1 2

Sample Output
1 1
這道題看似是一個圖論題， 然而仔細一看就水的不行啦。 如果 1 和點 n 沒有直接相連的路徑， 那么最短路徑就是這一條。 否則，最短路徑還是這一條。 但是連線的方案確是任意亂連都可以。有 n*（n-1）/2個連法。
當時對題意理解錯啦：  理解為添加一條路徑使1到其他點路徑的總和最小。 （嗚嗚嗚嗚~~~~）

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int m, n;
    while(~scanf("%d%d", &n, &m))
    {
        int u, v;
        int ok = 0;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d", &u, &v);
            if((u==1&&v==n)||(v==1&&u==n))
            ok = 1;
        }
        if(!ok) printf("%d %d\n",1, 1);
        else printf("%d %d\n",1, n*(n-1)/2);
    }
    return 0;
} 
 