0808

11404.cpp

#include <stdio.h>

int graph[105][105];

int main()
{
	int n, m;
	scanf("%d", &n);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (graph[a][b] == 0 || graph[a][b] > c) {
			graph[a][b] = c;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (j == k) continue;
				if (graph[j][i] != 0 && graph[i][k] != 0 && (graph[j][k] == 0 || graph[j][k] > graph[j][i] + graph[i][k])) {
					graph[j][k] = graph[j][i] + graph[i][k];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) {
			printf("%d ", graph[i][j]);
		}
		printf("\n");
	}

	return 0;
}

11657.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int dis[505];
vector<pair<int, int> > graph[505];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		int j;
		for (j = 0; j < graph[a].size(); j++) {
			if (graph[a][j].first == b) {
				graph[a][j].second = graph[a][j].second < c ? graph[a][j].second : c;
				break;
			}
		}
		if (j >= graph[a].size()) {
			graph[a].push_back(make_pair(b, c));
		}
	}

	for (int i = 1; i <= n; i++) {
		dis[i] = 987654321;
	}

	dis[1] = 0;
	int cycle = false;
	for (int i = 0; i < n; i++) {		// 경로의 길이 : i
		for (int j = 1; j <= n; j++) {		// 시작점
			for (int k = 0; k < graph[j].size(); k++) {		// 연결된 간선
				if (dis[j] < 987654321 && dis[graph[j][k].first] > dis[j] + graph[j][k].second) {
					dis[graph[j][k].first] = dis[j] + graph[j][k].second;
					if (i == n - 1) cycle = true;
				}
			}
		}
	}
	if (cycle) {
		printf("-1");
	}
	else {
		for (int i = 2; i <= n; i++) {
			if (dis[i] < 987654321) printf("%d\n", dis[i]);
			else printf("-1\n");
		}
	}

	

	return 0;
}

1753.cpp

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

priority_queue< pair<int, int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
vector< pair<int, int> > graph[20005];
int dis[20005];
int found[20005];
int via[20005];
int n, e, s;

int main()
{
	scanf("%d %d", &n, &e);
	scanf("%d", &s);
	for (int i = 0; i < e; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a].push_back(make_pair(b, c));
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = 987654321;
		found[i] = 0;
		via[i] = 0;
	}
	dis[s] = 0;

	pq.push(make_pair(0, s));
	for (int i = 0; i < n; i++) {
		int x = -1;
		while (!pq.empty()) {
			x = pq.top().second;
			if (found[x] == 0) {
				break;
			}
			pq.pop();
		}

		if (!pq.empty()) pq.pop();
		found[x] = 1;
		for (int j = 0; j < graph[x].size(); j++) {
			int node = graph[x][j].first, weight = graph[x][j].second;
			if (dis[node] > dis[x] + weight) {
				dis[node] = dis[x] + weight;
				via[node] = x;
				pq.push(make_pair(dis[node], node));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dis[i] >= 987654321) printf("INF\n");
		else printf("%d\n", dis[i]);
	}
	return 0;
}

1916.cpp

#include <stdio.h>

int n, m;
int graph[1005][1005];
int dis[1005];
int found[1005];
int via[1005];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= 1000; i++) {
		for (int j = i + 1; j <= 1000; j++) {
			graph[i][j] = graph[j][i] = 1987654321;
		}
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (graph[a][b] > c) {
			graph[a][b] = c;
		}
	}
	int s, f;
	scanf("%d %d", &s, &f);

	for (int i = 0; i <= n; i++) {
		dis[i] = 1987654321;
		found[i] = 0;
		via[i] = 0;
	}
	dis[s] = 0;

	for (int i = 0; i < n; i++) {
		int x = 0;
		for (int j = 1; j <= n; j++) {
			if (found[j] == 0 && dis[x] > dis[j]) {
				x = j;
			}
		}
		if (x == -1) break;
		found[x] = 1;
		for (int j = 1; j <= n; j++) {
			if (dis[j] > dis[x] + graph[x][j]) {
				dis[j] = dis[x] + graph[x][j];
				via[j] = x;
			}
		}
	}
	printf("%d", dis[f]);

	return 0;
}

2206.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
int arr[1005][1005];
int st[1005][1005], ed[1005][1005];
int Qx[1000 * 1000 + 5], Qy[1000 * 1000 + 5];

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= m + 1; j++) {
			st[i][j] = ed[i][j] = 99999;
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		arr[i][0] = arr[i][m + 1] = 1;
	}
	for (int i = 0; i <= m + 1; i++) {
		arr[0][i] = arr[n + 1][i] = 1;
	}

	int head = 0, tail = 1;
	Qx[0] = Qy[0] = 1;
	st[1][1] = 1;
	while (head != tail) {
		for (int i = 0; i < 4; i++) {
			int tx = Qx[head] + dir[i][0], ty = Qy[head] + dir[i][1];
			if (st[tx][ty] > st[Qx[head]][Qy[head]] + 1) {
				st[tx][ty] = st[Qx[head]][Qy[head]] + 1;
				if (arr[tx][ty] == 0) {
					Qx[tail] = tx; Qy[tail++] = ty;
				}
			}
		}
		head++;
	}

	head = 0; tail = 1;
	Qx[0] = n; Qy[0] = m;
	ed[n][m] = 1;
	while (head != tail) {
		for (int i = 0; i < 4; i++) {
			int tx = Qx[head] + dir[i][0], ty = Qy[head] + dir[i][1];
			if (ed[tx][ty] > ed[Qx[head]][Qy[head]] + 1) {
				ed[tx][ty] = ed[Qx[head]][Qy[head]] + 1;
				if (arr[tx][ty] == 0) {
					Qx[tail] = tx; Qy[tail++] = ty;
				}
			}
		}
		head++;
	}

	int ans = 99999;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (ans > st[i][j] + ed[i][j] - 1) {
				ans = st[i][j] + ed[i][j] - 1;
			}
		}
	}
	if (ans >= 99999) {
		printf("-1");
		return 0;
	}
	printf("%d", ans);
	return 0;
}