DS实验题 sights

算法与数据结构实验题 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

巴特西

DS实验题 sights

最新文章

热门文章