题意：众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
勇太有一张nn个点mm条边的无向图，每一条边的长度都是1。现在他想再在这张图上连上一条连接两个不同顶点边，使得1号点到nn号点的最短路尽可能的短。现在他想要知道最短路最短是多少，以及再保证最短路最短的情况下，他有多少种连边的方案。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
简单题。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
int n,m;
int main()
{
while(~scanf("%d%d",&n,&m)){
int flag=0;
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
if(x==1&&y==n)flag=1;
if(x==n&&y==1)flag=1;
}
if(!flag)puts("1 1");
else printf("1 %d\n",n*(n-1)/2);
}
return 0;
}
|
