node p = q.top();
q.pop();
int len = v[p.x].size();
for(i = 0;i < len; i++)//松弛
{
node t = v[p.x][i];
if(dis[t.x] > p.dis + t.dis)
{
dis[t.x] = p.dis + t.dis;
//t.x =
t.dis = dis[t.x];
q.push(t);
}
}
}
}
int main()
{
node no;
int x,y,z;
scanf("%d %d",&n,&m);
while(m--)
{
scanf("%d %d %d",&x,&y,&z);
no.x = y;
no.dis = z;
v[x].push_back(no);
no.x = x;
v[y].push_back(no);
}
dijkstra(1);
printf("%d\n",dis[n]);
return 0;
}
Bovine Bridge Battle
给你很多点 求有多少个平行四边形 每2个点求出中点 最后求中点一样的有多少对
[html]
#include
#include
#include
using namespace std;
struct node
{
double x,y;
}p[1010],a[1000010];
bool cmp(node a,node b)
{
if(a.x!=b.x)
return a.x
return a.y < b.y;
}
int main()
{
double x,y;
__int64 i,j,sum = 0,k = 0,count,n;
scanf("%I64d",&n);
for(i = 0;i < n; i++)
{
scanf("%lf %lf",&p[i].x,&p[i].y);
for(j = 0;j < i; j++)
{
a[k].x = p[i].x + p[j].x;
a[k].y = p[i].y + p[j].y;
k++;
}
}
sort(a,a+k,cmp);
for(i = 1,count = 1;i < k; i++)
{
if(a[i].x != a[i-1].x || a[i].y != a[i-1].y)
{
sum += count * (count - 1) / 2; //组合每2个可以组成 1个平行四边形
count = 1;
}
else
count++;
}
printf("%I64d\n",sum);
return 0;
}
Lucky Charms
水题 看懂就行
Pathfinding
求下一秒哪几个点可以走到 输出记得排序就行
[html]
include
#include
#include
using namespace std;
int a[110][110];
int map[110];
vector v[110];
int main()
{
int m,i,j,n,k,t;
scanf("%d %d",&n,&m);
for(i = 1;i <= n; i++)
{
for(j = 1;j <= n; j++)
{
scanf("%d",&a[i][j]);
}
}
map[m] = 1;
v[0].push_back(m);
i = 1;
while(1)
{
int len = v[i-1].size();
for(j = 0;j < len; j++)
{
for(k = 1;k <= n; k++)
{
if(a[v[i-1][j]][k] && !map[k])
{
map[k] = 1;
v[i].push_back(k);
}
}
}
if(v[i].size() == 0)
break;
i++;
}
k = i;
for(i = 0;i < k; i++)
{
sort(v[i].begin(),v[i].end());
for(j = 0;j < v[i].size(); j++)
{
if(j)
printf(" ");
printf("%d",v[i][j]);
}
puts("");
}
return 0;
}
A spiral walk
水题啊 那图是骗人的啊 没什么格式啊 直接输出好了 坑到家了
[html]
#include
int a[800][800];
int main()
{
int n,i,j,x,k;
scanf("%d",&n);
k = 1;
x = 1;
a[i = 1][j = 1] = 1;
while(x < n*n)
{
while(j+1 <= n && !a[i][j+1])
{
if(b[j+1] < x+1)
b[j+1] = x+1;
a[i][++j] = ++x;
}
while(i+1 <= n && !a[i+1][j])
{
if(b[j] < x+1)
b[j] = x+1;
a[++i][j] = ++x;
}
while(j>1 && !a[i][j-1])
{
if(b[j-1] < x+1)
b[j-1] = x+1;
a[i][--j] = ++x;
}
while(i>1 && !a[i-1][j])
{
if(b[j] < x+1)
b[j] = x+1;
a[--i][j] = ++x;
}
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(j - 1)