acm第一阶段练习

[珠浩 杨]

先做下测试先。。。看一下大家的时间。。。。今天星期二，大家先去把“最短路(Floyd、Dijstra,BellmanFord) ”这个算法搞出
来。。。可以自己打一个出来，也可以上网去查资料弄出来。。。之后自己打个十到二十遍（随你打），伟儒师兄要记录好完成的时间以及完成的量。。。
这是一个测试，但也是最开始最重要的一个。。。从现在发出这封邮件到收到我算一天的时间，明天星期三开始做，看大家的完成了。。。

From ： 杨珠浩

2011年11月15号

[Qzi]

/* POJ 2387
*  Second Modified by Qzi
*/

#include <cstdio>
#include <queue>
#include <list>
#include <utility>
#include <limits.h>

using namespace std;

const int INF = INT_MAX;        // 假设为无穷远

// <totalCostToThisVertex and vertex>
typedef pair<int, int> pii;       

// <vertex and dis>
typedef pair<int, int> edge;    // 边所指向顶点的权重

int T,    //    Tails
    N;    //  从第 N 个顶点赶回 第 1 个顶点

int totalCostToThisVertex[1001];  

          // 记录当前点到原点的路径开销
bool visited[1001];        // 1000+1 是为去除下标0 ， 直接从1 开始
list<edge> Vertex[1001];        // 当前节点到目标节点的权重

priority_queue<int, vector<pii>, greater<pii> > pq;    // 这是最小堆

void readData()
{
    int f,    // 前向的顶点
        t,    // 前向顶点所指向的目标顶点
        w;    // 以上两点路径所花的权重
    int fTest[5] = {1, 2, 3, 4, 1};    // 免输入测试数据
    int tTest[5] = {2, 3, 4, 5, 5};   
    int wTest[5] = {20, 30, 20, 20, 100};

    for(int i = 0; i < T; i++)
    {
        //scanf("%d%d%d", &f, &t, &w); 
        f = fTest[i];
        t = tTest[i];
        w = wTest[i];
        printf("%d %d %d\n", f, t, w);       
        Vertex[f].push_front(make_pair(t, w));    // 存的是前向顶点的出度
        Vertex[t].push_front(make_pair(f, w));    // 存的是目标顶点的入度
    }
}

void init()
{
    for(int i = 1; i <= N; i++)
    {
        totalCostToThisVertex[i] = INF;        // 无穷远， 表示不可连通
        visited[i] = false;                    // 初始一个未访问数组
    }
    totalCostToThisVertex[N] = 0;            // 起点开销为 0
                                            // 这道题要从 landmark[5] 赶回 landmark[1]
    pq.push(make_pair(totalCostToThisVertex[N], N));    // 第一个入队列的顶点
}

void dijkstra()
{
    while(!pq.empty())    // 查看优先级队列是否为空
    {   
        pii u = pq.top();    // 记录队头的元素
        pq.pop();            // 队头出队， 以此来推进当前顶点

        int currentVertex = u.second;    //  记录对头顶点 ，也就是开销最少的路径
        if(visited[currentVertex])
        {
            continue;   
        }// 如果顶点已经访问过就掠过进入下一个循环

        visited[currentVertex] = true;        // 标记为访问过
        list<edge> es = Vertex[currentVertex];    // 当前顶点
        list<edge>::iterator it;

        printf("checking %d's edges\n", currentVertex);
        for(it = es.begin(); it != es.end(); it++)
        {    // 遍历当前顶点的出度
            int targetVertex = it->first;
            printf("checking %d\n", targetVertex);
            // 松弛技术
            if (totalCostToThisVertex[targetVertex] >
                totalCostToThisVertex[currentVertex] + it->second)
            {
                totalCostToThisVertex[targetVertex] =
                    totalCostToThisVertex[currentVertex] + it->second;
                pq.push(
                    make_pair(
                        totalCostToThisVertex[targetVertex],
                        targetVertex
                        ) //
                    );
            }// end if
        }// end for
    }// end while
    printf("%d\n", totalCostToThisVertex[1]);        // 打印出从起点Landmarks[5] 到 Landmarks[1] 最短路径的开销
}

int main()
{
    //scanf("%d%d", &T, &N);   
    T = 5;    // 免输入测试数据
    N = 5;
    readData();
    init();
    dijkstra();

    getchar();
}


/*
Til the Cows Come Home
Time Limit: 1000MS        Memory Limit: 65536K
Total Submissions: 16537        Accepted: 5461
Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
Input

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.
Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.
Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output

90
Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

*/

Reference：
1.最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++) <-http://www.wutianqi.com/?p=1890
2.Til the Cows Come Home <-http://poj.org/problem?id=2387

2011/11/15 珠浩 杨 <clear...@gmail.com>

--
Your biological and technological distinctiveness will be added to our own. Resistance is futile.

[Qzi]

收到

2011/11/15 珠浩 杨 <clear...@gmail.com>

[杨珠浩]

收到。。

2011/11/15 珠浩 杨 <clear...@gmail.com>

先做下测试先。。。看一下大家的时间。。。。今天星期二，大家先去把“最短路(Floyd、Dijstra,BellmanFord) ”这个算法搞出

[杨珠浩]

新的附件（Dijkstra）

2011/11/15 珠浩 杨 <clear...@gmail.com>

[Andrew Chui]

理解算法原理，自己没能用程序实现，主要是研究对以下程序代码和注释


//图的定义类
package Dijkstra;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
/**
 * 定义简单图,为最短路径算法准备
 *
 */
public class SimplGraph {
 
    public int key;//存放节点值
  
    public List<Integer> nearNode;//存放相邻节点的集合
   
    public Map<String,Integer> weight; //两个节点间的距离
    //初始化参数
    public SimplGraph(int key){
        this.key = key;
        nearNode = new ArrayList<Integer>();//创建列表来存放节点
        weight = new HashMap<String,Integer>();//用来存放节点到节点的距离
    }
    //添加邻节点
    public void addNode(int node,int lengh){
        //将这个节点添加入到邻节点列中
        nearNode.add(node);
        //记录类另个节点间的距离
        weight.put(Integer.toString(node), lengh);
    }
}


//算法的实现类
package Dijkstra;

import java.util.Iterator;

/**
 * 最短路径计算(基本算法)
 *
 */
public class Dijkstra {
 
    SimplGraph[] total;

    //初始化数据
 
    public Dijkstra(){
        total = new SimplGraph[6];//创建一个6顶点的图
        //设置一个图
        int a = 0,b = 1,c = 2,d = 3,e = 4,f = 5 ;
        SimplGraph Sa = new SimplGraph(0);
        SimplGraph Sb = new SimplGraph(9999);
        SimplGraph Sc = new SimplGraph(9999);
        SimplGraph Sd = new SimplGraph(9999);
        SimplGraph Se = new SimplGraph(9999);
        SimplGraph Sf = new SimplGraph(9999);
        //设置每个节点的邻节点及权值
        Sa.addNode(b,1); //表示a到b为1，后面原理一样
        Sa.addNode(c,4);
        Sa.addNode(d,7);
      
        Sb.addNode(a,1);
        Sb.addNode(c,1);
        Sb.addNode(e,3);
      
        Sc.addNode(a,4);
        Sc.addNode(b,1);
        Sc.addNode(d,3);
        Sc.addNode(f,6);
      
        Sd.addNode(a,7);
        Sd.addNode(c,3);
        Sd.addNode(f,9);
      
        Se.addNode(b,3);
        Se.addNode(f,5);
      
        Sf.addNode(c,6);
        Sf.addNode(d,9);
        Sf.addNode(e,5);
      
        //设置每个节点的索引
        total[a] = Sa;
        total[b] = Sb;
        total[c] = Sc;
        total[d] = Sd;
        total[e] = Se;
        total[f]= Sf;
    }

    public void minPath(){
        for (int i = 0; i < total.length; i++) {
            Iterator it = total[i].nearNode.iterator();//迭代
            while(it.hasNext()){//判断是否还没迭代完
                //得到节点的数字索引
                int node = (Integer)it.next();
                //通过索引得到节点的类
                SimplGraph sg = total[node];
                //对此节点进行最短路径计算
                if(sg.key>total[i].key+total[i].weight.get(Integer.toString(node)))
                    sg.key = total[i].key+total[i].weight.get(Integer.toString(node));
            }
        }
    }
  
  
    public static void main(String[] args){
        Dijkstra d = new Dijkstra();
        d.minPath();//执行计算方法
        SimplGraph[] s = d.total;
        //有向图
        System.out.println("   {a,b,c,d,e,f}"+"\n"+"a=0{0,1,4,7,x,x}"+"\n"+"b=1{1,0,1,x,3,x}"+"\n"+"c=3{4,1,0,3,x,6}"+"\n"+"d=4{7,x,3,0,x,9}"+"\n"+"e=5{x,3,x,x,0,5}"+"\n"+"f=6{x,x,6,9,x,0}");
        for (int i = 0; i < s.length; i++) {
            System.out.println("节点 "+i+"：最短路径为 "+s[i].key);
           
        }
    }
}
原文：http://www.99inf.net/SoftwareDev/Java/54407.htm
知识参考：http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/

[Qzi]

Java 还不怎么熟悉，那份代码在
63|          Iterator it = total[i].nearNode.iterator();//迭代

有一个警告如下：
Description    Resource    Path    Location    Type
Iterator is a raw type. References to generic type Iterator<E> should be parameterized    Dijkstra.java    /Dijsktra/src/Dijkstra    line 63    Java Problem

怎么处理掉会好捏 ？

2011/11/17 Andrew Chui <colorfu...@gmail.com>

[Andrew Chui]

虽然程序执行正常，但是那样些的确不规范，Iterator<E>，是泛型。后面的E要指定是要被迭代的 nearNode 的类型（Integer）就可以了。