记录编号	455216	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	eliot	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-10-01 16:20:56	内存使用	0.35 MiB

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#include <string>

#define MAXINT 20000

using namespace std;

int n, m, v, g[100][100], lowcost[100], mst[100];
bool flag[100];
ifstream fin;
ofstream fout;

void djs(int v1) {
	for (int i = 0; i < n; ++i) {
		lowcost[i] = g[mst[i] = v1][i];
		flag[i] = false;
	}
	lowcost[v1] = MAXINT;
	flag[v1] = true;
	for (int i=1;i<n;++i) {
	    int minlowcost = MAXINT,k;
        for (int j=0;j<n;++j)
            if (!flag[j] && lowcost[j] < minlowcost)
                minlowcost = lowcost[k = j];
        flag[k] = true;
        for (int j=0;j<n;++j)
            if (!flag[j] && (g[k][j] + lowcost[k]) < lowcost[j])
                lowcost[j] = g[k][j] + lowcost[mst[j] = k];
	}
}

void walk(int i) {
    if (i != v)
        walk(mst[i]);
        fout << i << " ";
}

void prin() {
    for (int i = 0; i < n; ++i) {
		fout << i << ":" << endl;
		if (lowcost[i] == MAXINT) fout << "no" << endl;
		else {
			fout << "path:";
			walk(i);
			fout << endl << "cost:" << lowcost[i] << endl;
		}
	}
}

int main() {
    fout.open("djs.out");
    fin.open("djs.in");
	int a, b, c;
	fin >> n >> m >> v;
	for (int i = 0; i < 100; ++i)
		for (int j = 0; j < 100; ++j)
			g[i][j] = MAXINT;
	for (int i = 0; i < m; ++i) {
		fin >> a >> b >> c;
		g[a][b] = c;
	}
	djs(v);
	prin();
	cout << "df";
	return 0;
}