Skip to content

11105: 【原1105】path

题目

题目描述

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

path

Description

以下摘自是某ACM队某次对话的某民间记载:

……

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

唰唰唰。画出了一张无向图。

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

指指点点。

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

队长画出了一条最短路径。

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

拿起笔指向其中一人。

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

笔尖一转。

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

……

记载到此结束。

我们对这段历史很有兴趣。现在已知上述队长画出的图,以及图中的S、T和各边的权值,求三人所要求的路线。

提示:没有学习过最短路径的同学可以上网查找一下相关资料,推荐使用SPFA或者dijkstra算法。

Input Format

输入的第一行包含一个不超过10的正整数T,表示数据的组数。 接下来有T个部分,每个部分的第一行包括四个正整数n、m、s、t,(1<=n<=1000,0<=m<=10000),s、t表示起点终点。接下来有m行,第i行描述第i条边的信息,所有权均为正整数,并且不超过32768,格式见样例,并且保证数据中的格式与样例一致。 顶点标号为1~n标号。

Output Format

输出包含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)
            addEdge(u, v, w);
    }
    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;
vector<Node> link[MAX_N];
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() {
    T = read();
    while (T--) {
        for (register int i = 0; i < n; ++i) link[i].clear();
        n = read(); m = read(); s = read(); t = read();
        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;
}