算法与数据结构实验题 6.3 sights
★实验任务
美丽的小风姑娘打算去旅游散心,她走进了一座山,发现这座山有 n 个景点, 由于山路难修,所以施工队只修了最少条的路,来保证 n 个景点联通,娇弱的小 风姑娘不想走那么长的山路,所以打算乘坐专用的交通工具。有的景点之间有路, 乘坐交通工具需要花费一定的金额。
由于到达景区之前已经花了一部分钱了,现在可爱的小风姑娘站在景点 1, 即根景点。按原计划她要去编号为 m 的景点,导游告诉她到景点 m 总共要花的钱 (包括来之前花的钱)。然而善变的小风姑娘突然想去景点 y(直接从景点 1 到 景点 y),所以她想要知道到景点 y 总共要花多少钱,作为程序员之花,她想用 代码来解决这个问题。
★数据输入
输入第一行为一个正整数 n 表示景点的数目,景点从 1 到 n 编号。
接下来 n-1 行,代表山路,每行三个整数 x,y,p,分别表示 x,y 景点间的路 费。
第 n+1 行一个整数 q 表示询问组数。每组数据独立互不相关。
紧跟着 q 行,每行三个整数 m,v,y,分别表示 m 景点的编号,到达 m 景点 的总花费 v,以及要求的 y 景点。
30%的数据 n<=20,p<=100,q<=10 70%的数据 n<=1000,p<=10000,q<=100 100%的数据 n<=100000,p<=1000000,q<=n
★数据输出
输出 q 行,每行一个整数表示题目要求的答案,由于答案可能很大,输出对 707063423 取余的结果。
输入示例：
4
1 2 5
1 3 6
2 4 4
2 284 362
输出示例
12 5
全WA代码，思路是最简单的建树：
//
// main.cpp
// sights
//
// Created by wasdns on 16/10/16.
// Copyright © 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
struct Tree {
Tree* l;
Tree* r;
int data;
int lcost;
int rcost;
};
struct nodes {
int a;
int b;
int cost;
bool flag;
}Node[100000];
Tree* Initial() {
Tree* header;
header = new Tree;
header -> l = NULL;
header -> r = NULL;
header -> data = -1;
header -> lcost = -1;
header -> rcost = -1;
return header;
}
int NodeCost(Tree* header, int Nodedata) {
queue<Tree*> q;
queue<int> int_q;
int_q.push(0);
Tree* turn;
q.push(header);
while (!q.empty()) {
turn = q.front();
q.pop();
int a = int_q.front();
if (turn -> data == Nodedata) {
return a;
}
if (turn -> l != NULL) {
if (turn -> l -> data != -1) {
q.push(turn -> l);
int_q.push(a + turn -> lcost);
}
}
if (turn -> r != NULL) {
if (turn -> r -> data != -1)
q.push(turn -> r);
int_q.push(a + turn -> rcost);
}
int_q.pop();
}
return -1;
};
Tree* CreatTree(Tree* header, int n) {
header = Initial();
queue<Tree*> q;
header -> data = 1;
q.push(header);
while (1)
{
int turn;
if (q.empty()) {
break;
}
Tree* tpoint = q.front();
turn = tpoint -> data;
q.pop();
int flag = 0; //有两个子节点
for (int i = 1; i <= n - 1; i++) {
if ( !Node[i].flag &&
( Node[i].a == turn || Node[i].b == turn ) ) { //父子相认
Node[i].flag = true;
//cout << "turn: " << turn << endl;
//cout << Node[i].a << " " << Node[i].b << endl;
Tree* newpoint;
newpoint = Initial();
if (Node[i].a == turn) {
newpoint -> data = Node[i].b;
}
else {
newpoint -> data = Node[i].a;
}
if (flag) {
tpoint -> r = newpoint;
tpoint -> rcost = Node[i].cost;
}
else {
tpoint -> l = newpoint;
tpoint -> lcost = Node[i].cost;
flag = 1;
}
q.push(newpoint);
}
}
}
return header;
}
void PrintTree(Tree* p) {
queue<Tree*> q;
q.push(p);
Tree* turn;
turn = Initial();
while (!q.empty()) {
turn = q.front();
q.pop();
cout << turn -> data << " ";
if (turn -> l != NULL) {
if (turn -> l -> data != -1)
q.push(turn -> l);
}
if (turn -> r != NULL) {
if (turn -> r -> data != -1)
q.push(turn -> r);
}
}
cout << endl;
}
int main() {
int n, i;
cin >> n;
for (i = 1; i <= n - 1; i++) {
cin >> Node[i].a >> Node[i].b >> Node[i].cost;
Node[i].flag = false;
}
Tree* header;
header = CreatTree(header, n);
//PrintTree(header);
int asktime;
cin >> asktime;
int pre, post, precost;
for (i = 1; i <= asktime; i++) {
cin >> pre >> precost >> post;
int mid = precost - NodeCost(header, pre);
cout << NodeCost(header, post) + mid << endl;
}
return 0;
}
AC代码，朝夕的做法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef __int64 LL;
const int maxn = 100010;
const LL mod = 707063423;
const LL INF = 0xffffffff;
struct Edge{
int u,v,next;
LL w;
}edge[2*maxn];
int tot = 0,head[maxn];
LL dis[maxn];
bool vis[maxn];
void addedge(int u,int v,LL w)
{
edge[tot].u = u;edge[tot].v = v;edge[tot].w = w;edge[tot].next = head[u];
head[u] = tot++;
}
void spfa(int N)
{
int i;
memset(vis,false,sizeof(vis));
for (i = 0;i <= N;i++) dis[i] = INF;
queue<int>que;
while (!que.empty()) que.pop();
dis[1] = 0;
que.push(1);
vis[1] = true;
while (!que.empty())
{
int u = que.front();
que.pop();
vis[u] = false;
for (i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if (dis[u] + edge[i].w < dis[v])
{
dis[v] = dis[u] + edge[i].w;
if (!vis[v])
{
que.push(v);
vis[v] = true;
}
}
}
}
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("2.txt","w",stdout);
int N,u,v,q,m,y,i;
LL w,cv;
memset(head,-1,sizeof(head));
scanf("%d",&N);
for (i = 0;i < N - 1;i++)
{
scanf("%d%d%I64d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
spfa(N);
scanf("%d",&q);
while (q--)
{
scanf("%d%I64d%d",&m,&cv,&y);
cv = (cv - dis[m] + mod)%mod;
printf("%I64d\n",(dis[y]%mod + cv%mod)%mod);
}
return 0;
}
可以参考下朝夕的博客：zzy19961112
2016/10/16