题目名称：疫苗运输 (Транспорт на вакцини)

来源：马其顿编程竞赛 (Macedonian Programming Contests)

题目背景

在一个北方的贫困国家，疫苗终于送达了。现在的任务是尽快将其从首都运送到其他城市。由于疫苗必须在极低温度下保存，而该国缺乏相关设备，因此决定只利用当前有积雪覆盖的道路进行运输。

然而，卫生部的会计师只愿意支付从首都到各城市的最短距离所产生的费用。如果为了走雪路而绕远路，超过了理论上的最短路径长度，政府将不予报销。

题目描述

给定一个包含 $N$ 个城市和 $M$ 条双向直接道路的地图：

1. 城市编号为 $1$ 到 $N$，首都是城市 $1$。
2. 每条道路包含四个参数：城市 $A$、城市 $B$、长度 $C$、积雪情况 $D$（$1$ 表示有雪，$0$ 表示无雪）。
3. 两个城市之间可能存在多条直接道路。
4. 保证从首都到任何城市都存在至少一条路径。

你的任务：

1. 计算从首都（城市 $1$）到城市 $N$ 的最短路径长度（不考虑是否有雪）。
2. 判断是否存在一条长度等于该最短路径长度、且全程都有雪的路径。

输入格式

• 第一行：两个整数 $N$ ($1 \le N \le 1000$) 和 $M$ ($N-1 \le M \le 3000$)。
• 接下来的 $M$ 行：每行四个整数 $A, B, C, D$。

输出格式

• 第一行：输出从城市 $1$ 到城市 $N$ 的最短距离。
• 第二行：如果存在一条满足最短距离且全程有雪的路径，输出 "DA"；否则输出 "NE"。

限制要求

• 时间限制：1.0 秒
• 内存限制：64 MB

样例分析

这道题（疫苗运输）的逻辑核心在于对比“无约束最短路”和“全雪路最短路”。以下是该题完整的输入输出样例及其详细的逻辑解释：

样例 1 (DA 情况)

输入 (1.in)

6 7
1 2 1 1
2 3 1 1
3 6 1 0
1 4 1 1
4 6 1 1
1 5 1 1
5 6 1 0

输出 (1.out)

2
DA

【样例 1 解释】

• 计算最短路径：从城市 1 到 6 的最短路径有几条：
  • 1 → 4 → 6：长度 $1 + 1 = 2$
  • 1 → 5 → 6：长度 $1 + 1 = 2$
  • 1 → 2 → 3 → 6：长度 $1 + 1 + 1 = 3$
  • 因此，全局最短距离是 2。
• 检查雪路：
  • 路径 1 → 4 → 6：1-4 有雪 ($D=1$)，4-6 有雪 ($D=1$)。整条路径都有雪且长度为 2。
  • 既然存在一条长度为 2 且全是有雪路段的路径，输出 DA。

样例 2 (NE 情况)

输入 (2.in)

6 7
1 2 1 1
2 3 1 1
3 6 1 1
1 4 1 0
4 6 1 1
1 5 1 1
5 6 1 0

输出 (2.out)

2
NE

【样例 2 解释】

• 计算最短路径：从城市 1 到 6 的最短路径依然是：
  • 1 → 4 → 6：长度 $1 + 1 = 2$
  • 1 → 5 → 6：长度 $1 + 1 = 2$
  • 全局最短距离依然是 2。
• 检查雪路：
  • 路径 1 → 4 → 6：1-4 没有雪 ($D=0$)。
  • 路径 1 → 5 → 6：5-6 没有雪 ($D=0$)。
  • 虽然路径 1 → 2 → 3 → 6 全程有雪，但它的长度是 3，大于最短距离 2。政府不报销超过最短距离的费用。
  • 由于没有任何一条长度为 2 的路径是全程有雪的，输出 NE。

数据规模提醒

• $N \le 1000$，$M \le 3000$。
• 城市间可能有重边（即 A 到 B 有多条路），在处理输入时，如果是 Dijkstra 算法，直接将所有边加入邻接表即可，算法会自动选择最优边。

版权信息：本题目整理自马其顿青少年编程竞赛（Macedonian Programming Contests）。版权归原赛事组委会所有。