11236: 【原1236】spath

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1236

Sample Input

``````7 12 3 6
1 2 2
3 1 4
1 4 1
2 4 3
4 5 2
2 5 10
3 6 3
4 6 -8
4 7 4
5 7 6
7 6 1
1 3 5
``````

Sample Output

``````-3                    //P387的例子
``````

Limits

0<n<=10 0<=m<=100

Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 10 + 10;

struct edgeNode {
int data;
int weight;
edgeNode *next;

edgeNode(int d = 0, int w = 0, edgeNode *n = 0)
: data(d), weight(w), next(n) {}
};

struct verNode {
int data;

verNode(int d = 0, edgeNode *h = 0) : data(d), head(h) {}
};

int n, m, Start, End, temp1, temp2, temp3, ans = 1e9;
verNode *nodes[maxN];
bool isVisited[maxN] = {0};

void DFS(int i, int w);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n >> m >> Start >> End;

for (int i = 1; i <= n; i++) {
nodes[i] = new verNode(i);
}

for (int i = 0; i < m; i++) {
cin >> temp1 >> temp2 >> temp3;
}

DFS(Start, 0);

cout << ans;

return 0;
}

void DFS(int i, int w) {
if (isVisited[i]) {
return;
}
if (i == End) {
ans = (w < ans) ? w : ans;
return;
}
isVisited[i] = 1;
while (p) {
DFS(p->data, w + p->weight);
p = p->next;
}
isVisited[i] = 0;
}
``````

yyong119's solution

``````#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

int n, m, s, e, temp1, temp2, temp3, now, next;
int dist[101];
int nextnode[101][101];
int nodeweight[101][101];
bool inque[101];
int main() {

queue<int> que;
memset(inque, false, sizeof(inque));
scanf("%d%d%d%d\n", &n, &m, &s, &e);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &temp1, &temp2, &temp3);
nextnode[temp1][++nextnode[temp1][0]] = temp2;
nodeweight[temp1][++nodeweight[temp1][0]] = temp3;
}
for (int i = 1; i <= n; i++) dist[i] = 10000000;
dist[s] = 0; inque[s] = true;
que.push(s);
while (!que.empty()) {
now = que.front();
for (int i = 1; i <= nextnode[now][0]; i++) {
next = nextnode[now][i];
if (dist[next] > dist[now] + nodeweight[now][i]) {
dist[next] = dist[now] + nodeweight[now][i];
if (!inque[next]) {
inque[next] = true;
que.push(next);
}
}
}
que.pop(); inque[now] = false;
}
printf("%d\n", dist[e]);
return 0;
}
``````

Zsi-r's solution

``````#include <iostream>
#include <queue>
using namespace std;

{
public:
void insert(int x, int y, int w);
void spfa(int start, int end) const;

private:
struct edgeNode
{
int end;
int weight;
edgeNode *next;

edgeNode(int e, int w, edgeNode *n = NULL)
{
end = e;
weight = w;
next = n;
}
};
struct verNode
{
int ver;

verNode(edgeNode *h = NULL) { head = h; }
};

int Vers, Edges;
verNode *verList;

void printPath(int start, int end, int prev[]) const;
};

{
this->Vers = vSize;

verList = new verNode[vSize];
for (int i = 0; i < vSize; i++)
{
verList[i].ver = d[i];
}
}

{
int i;
edgeNode *p;

for (i = 0; i < this->Vers; i++)
while ((p = verList[i].head) != NULL)
{
delete p;
}
delete[] verList;
}

void adjListGraph::insert(int x, int y, int w)
{
int u = x - 1, v = y - 1;
++this->Edges;
}

void adjListGraph::printPath(int start, int end, int prev[]) const
{
if (start == end)
{
cout << verList[start].ver;
return;
}
printPath(start, prev[end], prev);
cout << ' ' << verList[end].ver;
}

void adjListGraph::spfa(int start ,int end) const
{
int *distance = new int[Vers];
int *prev = new int[Vers];
queue<verNode> que;
bool *inQue = new bool [Vers];

int sNo,i;
edgeNode *p;
verNode v;

for (i =0;i<Vers;i++){
distance[i] = 1e5+5;
inQue[i] = false;
}

sNo = start-1;
distance[sNo] = 0;
que.push(verList[sNo]);
inQue[sNo] = true;

while(!que.empty()){
v = que.front();
que.pop();
inQue[v.ver-1] = false;
for (p = verList[v.ver-1].head;p!=NULL;p = p->next){
if (distance[v.ver-1]+p->weight < distance[p->end]){
distance[p->end] = distance[v.ver-1] + p->weight;
prev[p->end] = v.ver-1;
if (!inQue[p->end])
que.push(verList[p->end]);
}
}
}

cout << distance[end-1]<<endl;
//printPath(start-1, end, prev);
}

int main()
{
int n, m, start, end, edgestart, edgeend, edgeweight;

cin >> n >> m >> start >> end;

int *verarray = new int[n];
for (int i = 0; i < n; i++)
{
verarray[i] = i + 1;
}