ACM学习历程—HDU5422 Rikka with Graph(贪心)
Yuta has a non-direct graph with n vertices and m
edges. The length of each edge is 1. Now he wants to add exactly an
edge which connects two different vertices and minimize the length of
the shortest path between vertice 1 and vertice n. Now he wants to know the minimal length of the shortest path and the number of the ways of adding this edge.
It is too difficult for Rikka. Can you help her?
For each testcase, the first line contains two numbers n,m(2≤n≤100,0≤m≤100).
Then m lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. There may be multiedges and self loops.
You can only add an edge between 1 and 2.
首先最小距离肯定是1,不可能比1还小。
其次最小距离肯定是1,因为只要连1和n就能达到1。
那么如果一开始1和n没有相连,那么连接1和n能达到1,否则均大于1。
如果1和n一开始就相连,那么随便连两条就OK,C(n, 2) = n*(n-1)/2。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#define LL long long using namespace std; int n, m;
bool dis[][]; int input()
{
if (scanf("%d%d", &n, &m) == EOF)
return false;
memset(dis, false, sizeof(dis));
int u, v;
for (int i = ; i < m; ++i)
{
scanf("%d%d", &u, &v);
dis[u][v] = dis[v][u] = true;
}
return true;
} void work()
{
printf("1 ");
if (dis[][n])
printf("%d\n", n*(n-)/);
else
printf("1\n");
} int main()
{
//freopen("test.in", "r", stdin);
while (input())
{
work();
}
return ;
}
最新文章
- Hadoop2.x的Eclipse插件编译与安装
- angular源码分析:angular中各种常用函数,比较省代码的各种小技巧
- java对象存储管理
- [BZOJ1220][POJ1091][HNOI2002]跳蚤
- Cocos开发中Visual Studio下HttpClient开发环境设置
- HDU 5925 Coconuts 【离散化+BFS】 (2016CCPC东北地区大学生程序设计竞赛)
- HDU1878 欧拉回路 - from lanshui_Yang
- iTextSharp使用字体设置摘录
- listview相关代码整理
- C图形库Easyx的使用
- c#发展前景
- Linux常用命令(第二版) --帮助命令
- linux-高并发与负载均衡-lvs-3种模型推导
- EASYUI combobox firefox 下取值为空的问题或不支持中文检索的问题
- 因mybatis逆向工程而产生的问题
- eclipse——JDK安装与环境变量配置步骤
- mui集成百度ECharts的统计图表以及清空释放图表
- M2 Daily SCRUM要求
- flutter实现(OutlineButton)线框按钮
- JVM(三)调优工具