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;
}