LeetCode 2642. 设计可以求最短路径的图类
原题链接
困难
作者:
我是java同学
,
2023-09-21 21:58:24
,
所有人可见
,
阅读 80
const int N = 110, INF = 0x3f3f3f3f;
int dist[N];
int g[N][N];
bool st[N];
class Graph {
public:
int n;
int dijkstra(int start, int end) {
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[start] = 0;
for (int i = 0; i < n; i ++ ) {
int t = -1;
for (int j = 0; j < n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for (int j = 0; j < n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[end] == INF) return -1;
return dist[end];
}
Graph(int _n, vector<vector<int>>& edges) {
memset(g, 0x3f, sizeof g);
n = _n;
for(auto&e: edges) {
int a = e[0], b = e[1], w = e[2];
g[a][b] = w;
}
}
void addEdge(vector<int> edge) {
g[edge[0]][edge[1]] = min(g[edge[0]][edge[1]], edge[2]);
}
int shortestPath(int start, int end) {
return dijkstra(start, end);
}
};
/**
* Your Graph object will be instantiated and called as such:
* Graph* obj = new Graph(n, edges);
* obj->addEdge(edge);
* int param_2 = obj->shortestPath(node1,node2);
*/