Description

Kolya has returned from a summer camp and now he's a real communication fiend. He spends all his free time on the Web chatting with his friends via ICQ. However, lately the protocol of this service was changed once again, and Kolya's client stopped working. Now, in order to communicate with his friends again, Kolya has to upgrade his client from version 1 to version n.
Kolya has found m upgrade programs on the Web. The i-th program upgrades the client from version xi to version yi and its size is dimegabytes. Each program can be installed on the corresponding version of the client only; it can't be installed on either earlier or later versions.
The first version, which is currently installed on Kolya's computer, is licensed, and many of the upgrade programs are pirate copies. If a pirate upgrade program is used, the client will always be pirated after that, whatever upgrade is used later. Some of the licensed upgrade programs can be installed on a pirate version of the client, and some of them can't. All the pirate upgrade programs can be installed on both licensed and pirate versions of the client.
Kolya is missing his friends very much, so he wants to download the necessary upgrade programs as soon as possible. Unfortunately, his Web connection is not very fast. Help Kolya determine the minimal total traffic volume necessary for upgrading the client from version 1 to version n. Kolya doesn't care if the final version n of his client is licensed or not.

Input

The first line contains space-separated integers n and m (2 ≤ n ≤ 104; 1 ≤ m ≤ 104).
Each of the following m lines describes one upgrade program in the form “xi yi di si”. Here, si is the type of the program: “Pirated”, “Cracked”, or “Licensed”. A cracked upgrade program is a licensed program that can be installed on a pirate version of the client, and a licensed program can't be installed on a pirate version. The numbers xi and yi mean that the program is installed on version xi of the client and upgrades it to version yi. The number di is the size of the program in megabytes (1 ≤ xi < yi ≤ n; 1 ≤ di ≤ 106). The data in each line are separated with exactly one space.

Output

If Kolya can upgrade the client from version 1 to version n, output “Online” in the first line and the minimal necessary total incoming traffic volume in the second line.
If it is impossible to upgrade the client, output “Offline”.

题目大意：有一个软件，要从1升级到n。每个升级有一个花费，用了P之后就不能再用L，求最小花费。

思路：正解是DP？不管。我们用最短路。建双层图，对于a→b L，在第一层建一条边。对于a→b P，从第一层的a建一条边到第二层的b，再从第二层的a建一条边到第二层的b。对于a→b C，第一层建一条边，第二层建一条边。再从第一层的n建一条边到第二层的n，费用为0。那么就保证了走过了P之后不会再走L，用SPFA求个最短路圆满解决。个人认为比D好写多了。我们要把图论发扬光大O(∩_∩)O~

代码（31MS）：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int MAXE = MAXN * ;

 int head[MAXN];

 int to[MAXE], next[MAXE], cost[MAXE];

 int n, m, st, ed, ecnt;

 void init() {

     memset(head, , sizeof(head));

     ecnt = ;

 }

 void add_edge(int u, int v, int c) {

     to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;

     //printf("%d->%d %d\n", u, v, c);

 }

 char s[];

 void input() {

     scanf("%d%d", &n, &m);

     int a, b, c;

     for(int i = ; i < m; ++i) {

         scanf("%d%d%d%s", &a, &b, &c, s);

         if(*s == 'P') {

             add_edge(a, b + n, c);

             add_edge(a + n, b + n, c);

         }

         if(*s == 'L') {

             add_edge(a, b, c);

         }

         if(*s == 'C') {

             add_edge(a, b, c);

             add_edge(a + n, b + n, c);

         }

     }

     add_edge(n, n + n, );

     st = , ed =  * n;

 }

 LL dis[MAXN];

 bool vis[MAXN];

 void SPFA() {

     memset(dis, , sizeof(dis));

     memset(vis, , sizeof(vis));

     queue<int> que; que.push(st);

     dis[st] = ;

     while(!que.empty()) {

         int u = que.front(); que.pop();

         vis[u] = false;

         for(int p = head[u]; p; p = next[p]) {

             int &v = to[p];

             if(dis[v] == - || dis[v] > dis[u] + cost[p]) {

                 dis[v] = dis[u] + cost[p];

                 if(!vis[v]) que.push(v);

                 vis[v] = true;

             }

         }

     }

 }

 void output() {

     if(dis[ed] == -) puts("Offline");

     else {

         puts("Online");

         cout<<dis[ed]<<endl;

     }

 }

 int main() {

     init();

     input();

     SPFA();

     output();

 }

最新文章

  1. java系统高并发解决方案-转
  2. CSS中的text-overflow:clip|ellipsis的使用
  3. UVa 221城市正视图（离散化）
  4. Brocade博科光纤交换机zone配置
  5. MYSQL常用内置函数详解说明
  6. JSP中&lt;img&gt;标签引用本地图片
  7. &quot;数学口袋精灵&quot;bug的发现
  8. 阿里云服务器上安装mysql的心路历程(博友们进来看看哦)
  9. poco网络库分析，教你如何学习使用开源库
  10. 欧几里得旅行商问题 java与c++实现
  11. ashx中session的使用
  12. java_linux_shell_定时kill 启动java程序
  13. Numpy中Meshgrid函数介绍及2种应用场景
  14. squid代理加用户认证
  15. django基础（一）
  16. 【Hbase学习之二】Hbase 搭建
  17. Asp.net core 学习笔记 ( Web Api )
  18. Python PIL模块笔记
  19. iOS 播放远程网络音乐的核心技术点
  20. CUDA C Programming Guide 在线教程学习笔记 Part 10【坑】

热门文章

  1. LeetCode12.整数转罗马数字 JavaScript
  2. MVVM及框架的双向绑定
  3. GoBelieve Android SDK接入备忘
  4. 设置Oracle数据库开机自启动
  5. JS基础——数组API之数组操作(filter、map、some、every、sort)
  6. ABAP术语-EDI (Electronic Data Interchange)
  7. 思维导图 XMind 8 Update 8 Pro for Mac 中文破解版
  8. 关于对连接数据库时出现1130-host “**” is not allowed to connect to this MySql/mariadb server 的错误解决方法
  9. mysql——查询重复数据，及删除重复数据只保留一条数据
  10. 迷你MyBank