一道很典型的最短路径的题目。
算法的思想来自于Dijkstra(迪杰斯特拉)算法,大家在这里对这个算法就不介绍了。
可以在学完最短经的算法后,用这道题目当做练手。。我的算法还需要优化一下,代码也需要优化,因为我的代码确实有点乱。。下面的代码仅供参考。。
题目的链接:http://soj.me/1703
#include <iostream> #include <stdio.h> #include <string> #include <cstring> #include <queue> #include <set> #include <vector> using namespace std; int dis[130][130]; struct Gra { int r; int c; friend bool operator <(Gra g1, Gra g2) { if(dis[g1.r][g1.c] < dis[g2.r][g2.c]) return true; } }; int main() { int t; int count = 1; while (cin >> t && t != 0) { int s[130][130]; for (int i = 1; i <= t; ++ i) { for (int j = 1; j <= t; ++ j) { cin >> s[i][j]; } } set<Gra> q; int know[130][130]; memset(know, 0, sizeof(know)); memset(dis, 9999999, sizeof(dis)); Gra tu[16900]; tu[1].r = 1; tu[1].c = 1; q.insert(tu[1]); Gra temp; int i = 2; dis[1][1] = s[1][1]; set<Gra>::iterator it; set<Gra>::iterator itt; while (!q.empty()) { it = q.begin(); temp = *it; itt = it; ++ it; Gra tem; for (; it != q.end(); ++ it) { tem = *it; if (dis[temp.r][temp.c] > dis[tem.r][tem.c]) { temp = tem; itt = it; } } q.erase(itt); know[temp.r][temp.c] = 1; if (temp.r == t && temp.c == t) { cout << "Problem " << count << ": " << dis[temp.r][temp.c] << endl; break; } if (temp.c - 1 >= 1) { tu[i].c = temp.c - 1; tu[i].r = temp.r; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.r - 1 >= 1) { tu[i].r = temp.r - 1; tu[i].c = temp.c; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.c + 1 <= t) { tu[i].c = temp.c + 1; tu[i].r = temp.r; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.r + 1 <= t) { tu[i].r = temp.r + 1; tu[i].c = temp.c; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } } ++ count; } //system("pause"); }
相关推荐
sicily 1562_LVM.cpp参考代码
中山大学 ACM sicily 1294 题目代码
sicily 1274的AC源码,通过且速度快,适合学生使用
本程序解决了Sicily平台上Queue的问题,有较好的可读性
这是C++解题常用的模板,对参加C++机试有较大帮助
本程序是中山大学sicily-1137-1145-1146-1147-1154-1157-1194的代码
西西里全部练习输入输出以及标准程序 超高精度浮点数的输出问题 关联数组
1005. 有向图边的分类 12图算法例题1000. sicily 1155. Can I Post the letteTime Limit: 1sec Mem
sicily 1817和1818的程序,各有两种方法,供参考。
本程序是中山大学sicily 1004-1007-1010-1014-1021 参考代码
本程序是中山大学sicily上1200-1221-1298-1324-1325的参考代码。
包括 sicily online judge 1149等部分题目,线性表,最小生成树,中缀转后缀并计算后缀表达式等。
sicily部分源代码,全都亲测,可通过
中大sicily online judge的刷题指南,里面介绍得很详细,不过,最近sicily好像不能外网访问了。
sicily(soj) 1022 1064 1310 1740 1876 1934 六题的源代码(数据结构综合应用题)
本cpp是sicily的1006的解题代码 这份代码以最简单的方式实现了它的功能要求 值得学习一番
112页的大礼包,sicily的部分ac代码。
Sicily的题目分类:各种题目的分类,大致方法,以及题目难度规范
sicily1007题答案,附代码解释,可以在平台上通过