传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2346

比较裸的最短路(' '     ) 水题又多了一道

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; const int maxn = 400010;
const int maxe = 2001000;
const int maxl = 510;
const int INF = 0x3f3f3f3f; struct edge {
int t, d;
edge* next;
}e[maxe * 2], *head[maxn]; int ne = 0; void addedge(int f, int t, int d) {
e[ne].t = t, e[ne].d = d, e[ne].next = head[f], head[f] = e + ne ++;
e[ne].t = f, e[ne].d = d, e[ne].next = head[t], head[t] = e + ne ++;
} struct node {
int pos, dis;
node(int a, int b) {
pos = a, dis = b;
}
}; bool operator < (const node &a, const node &b) {
return a.dis > b.dis;
} priority_queue <node> q;
int dis[maxn]; void dijkstra(int s, int t) {
memset(dis, INF, sizeof(dis)); dis[s] = 0;
for(int i = s; i <= t; ++ i) q.push(node(i, dis[i]));
while(!q.empty()) {
node x = q.top(); q.pop();
if(x.dis != dis[x.pos]) continue;
for(edge* p = head[x.pos]; p; p = p-> next)
if(dis[p-> t] > dis[x.pos] + p-> d)
dis[p-> t] = dis[x.pos] + p-> d, q.push(node(p-> t, dis[p-> t]));
}
} int n, m; int getpos(int x, int t) {
return (x - 1) * (m + 1) + t;
} char s[maxl]; void sov() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
for(int j = 1; j <= m; ++ j) {
if(s[j] == '/') addedge(getpos(i, j), getpos(i + 1, j + 1), 1), addedge(getpos(i + 1, j), getpos(i, j + 1), 0);
else addedge(getpos(i, j), getpos(i + 1, j + 1), 0), addedge(getpos(i + 1, j), getpos(i, j + 1), 1);
}
}
dijkstra(getpos(1, 1), getpos(n + 1, m + 1));
if(dis[getpos(n + 1, m + 1)] == INF) printf("NO SOLUTION\n");
else printf("%d\n", dis[getpos(n + 1, m + 1)]);
} int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
sov();
return 0;
}

最新文章

  1. oracle in VS or效率
  2. 表格边框css
  3. C#基础知识系列六(静态类和静态类成员)
  4. 最短路径算法(Dijkstra算法、Floyd-Warshall算法)
  5. RabbitMQ 原文译02--工作队列
  6. linux patch
  7. php+mysql+pdo连接数据库
  8. ASP无惧上传类不能上传中文双引号文件及ASP函数InStr存在bug
  9. jquery解决onmouseover和onmouseout合用的bug问题
  10. drupal7 sql接口笔记
  11. iOS学习笔记(02) - 关键字 __kindof
  12. MySQL实现自动使用uuid作为主键以及解决不能调用触发器的一点思路
  13. C# 委托高级应用----线程——创建无阻塞的异步调用(二)
  14. 关键字-super
  15. 4 扩展库Scipy
  16. MacOS安装Go2Shell
  17. 《剑指offer》顺时针打印矩阵
  18. [CF536D]Tavas in Kansas
  19. 机器学习(二)--------单变量线性回归(Linear Regression with One Variable)
  20. 如何开始DDD(续)

热门文章

  1. spring-boot 定时任务案例
  2. 【2019 Multi-University Training Contest 2】
  3. 【HDOJ6579】Operation(线性基)
  4. SSM - 全局跨域处理
  5. CentOS 如何将.deb 文件 转换.rpm, centos安装deb包
  6. spring-cloud config配置中心
  7. &lt;读书笔记&gt;Javascript系列之6种继承(面向对象)
  8. 关于列表倒序输出的几种方法——python第7天
  9. JMeter的那些问题
  10. redux请求数据流程