# 11105: 【原1105】path

### 题目描述

author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1105

# path

## Description

……

”接下来来讨论一下关于如何吃饭的问题。“

”我们现在处于S点，食堂处于T点。“

”本来吃饭是个很简单的问题，这条路是最短路径，我们顺着走过去就好。“

”但是你们两个非要提出古怪的要求。“

”首先是你，想要走一条人最少的路线，让我感到非常头疼，因为这意味着我们可能要绕很远的一段路。“

”然后是你，居然非要走一条最阴暗的路线，我已经完全不能够理解你在思考些什么了。“

……

## Sample Input

``````1
3 3 1 3
Name: Short but crowd road, From: 1, To: 2, Length: 1, People number: 10, Light: 1;
Name: Normal road, From: 2, To: 3, Length: 1, People number: 1, Light: 1;
Name: Long but not crowd road, From: 1, To: 3, Length: 10, People number: 1, Light: 1;
``````

## Sample Output

``````2 1 1
``````

## FineArtz's solution

``````/* path */
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 400000000;

int a[1005][1005][3] = {0};

inline int getNum(char *s){
int i = 0;
while (i < strlen(s) && !isdigit(s[i]))
++i;
int ret = 0;
while (i < strlen(s) && isdigit(s[i])){
ret = ret * 10 + s[i] - '0';
++i;
}
return ret;
}

inline void addEdge(int u, int v, int *w){
for (int i = 0; i < 3; ++i){
if (a[u][v][i] > w[i]){
a[u][v][i] = w[i];
a[v][u][i] = w[i];
}
}
}

int dijkstra(int n, int m, int k){
bool vis[10005] = {0};
int dis[10005] = {0};
int q[10005], front = 0, rear = 0;
for (int i = 1; i <= n; ++i)
dis[i] = INF;
dis[1] = 0;
vis[1] = true;
q[rear++] = 1;
while (front != rear){
int x = q[front++];
vis[x] = false;
for (int i = 1; i <= n; ++i){
if (x != i){
if (dis[i] > dis[x] + a[x][i][k]){
dis[i] = dis[x] + a[x][i][k];
if (!vis[i]){
q[rear++] = i;
vis[i] = true;
}
}
}
}
}
return (dis[n] != INF ? dis[n] : -1);
}

void solve(int n, int m, int s, int t){
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j)
for (int k = 0; k < 3; ++k)
a[i][j][k] = INF;
for (int i = 1; i <= m; ++i){
char ss[1000];
int len;
int u, v, w[3];
char ch;
len = 0;
while ((ch = getchar()) != ';'){
ss[len++] = ch;
}
ss[len] = '\0';
//cout << ss << endl;
auto p = strstr(ss, "From: ");
u = getNum(p);
p = strstr(ss, "To: ");
v = getNum(p);
p = strstr(ss, "Length: ");
w[0] = getNum(p);
p = strstr(ss, "People number: ");
w[1] = getNum(p);
p = strstr(ss, "Light: ");
w[2] = getNum(p);
if (u == 1)
u = s;
else if (u == s)
u = 1;
else if (u == n)
u = t;
else if (u == t)
u = n;
if (v == 1)
v = s;
else if (v == s)
v = 1;
else if (v == n)
v = t;
else if (v == t)
v = n;
if (u != v)
}
for (int i = 0; i < 3; ++i)
cout << dijkstra(n, m, i) << ' ';
cout << '\n';
}

int main(){
int tt;
cin >> tt;
while (tt--){
int n, m, s, t;
cin >> n >> m >> s >> t;
solve(n, m, s, t);
}
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <deque>
#include <vector>
#include <cstring>
#define MAX_N 1010
using namespace std;
struct Node {
int tar, val[3];
Node(int a = 0, int b = 0, int c = 0, int d = 0): tar(a) {
val[0] = b; val[1] = c; val[2] = d;
}
};
int T, n, m, s, t;
bool inque[MAX_N];
int dist[MAX_N];
deque<int> q;
inline int read() {
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
void spfa(int idx) {
q.push_back(s);
while (!q.empty()) {
int cur = q.front(); q.pop_front(); inque[cur] = false;
for (register int i = 0; i < link[cur].size(); ++i) {
int next = link[cur][i].tar, cost = link[cur][i].val[idx];
if (dist[cur] + cost < dist[next]) {
dist[next] = dist[cur] + cost;
if (!inque[next]) {
if (!q.empty() && dist[next] >= dist[q.front()]) q.push_back(next);
else q.push_front(next);
inque[next] = true;
}
}
}
}
}
int main() {
while (T--) {
for (register int i = 0; i < n; ++i) link[i].clear();
for (register int i = 0; i < m; ++i) {
char ch; int data[5];
for (int j = 0; j < 5; ++j) data[j] = read();
link[data[0]].push_back(Node(data[1], data[2], data[3], data[4]));
link[data[1]].push_back(Node(data[0], data[2], data[3], data[4]));
}
// calc minimun length
memset(dist, 0x3f3f3f3f, sizeof(dist)); dist[s] = 0;
memset(inque, false, sizeof(inque));
spfa(0);
printf("%d ", dist[t]);
// calc minimun people
memset(dist, 0x3f3f3f3f, sizeof(dist)); dist[s] = 0;
memset(inque, false, sizeof(inque));
spfa(1);
printf("%d ", dist[t]);
// calc minimun light
memset(dist, 0x3f3f3f3f, sizeof(dist)); dist[s] = 0;
memset(inque, false, sizeof(inque));
spfa(2);
printf("%d\n", dist[t]);
}
return 0;
}
``````