Skip to content

11236: 【原1236】spath

题目

题目描述

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

Description

终于到了最短路径部分的内容,想必你已经很累了。但还是请坚持,胜利就在前方。

如果你没有去听课,或者是觉得“最短路径”这个名字很陌生,那么请先返回376页,把概念先扫一遍(书上的介绍流程:无权图(搜索)->加权图(dijkstra单源的)->带负权的图(spfa算法)->floyd算法(多源))在这一题中,我们要求实现带负权的单源最短路径算法。由于带负权,dijkstra算法边不能再使用(原因请看P387),所以我们要求利用邻接表,通过搜索算法完成(事实上解决这个问题的最好算法是SPFA算法,P387有它的介绍。如果你有兴趣,当然也可以用它。)。

给定带负权的有向图,起点start,终点end,请计算由start到end的最短路径(数据保证不出现负环)

请不要使用floyd算法。

为简化题目,我们约定:用正整数1,2,3……n来表示每个结点的ID(编号)

Input Format

第1行:n m start end //正整数n ,代表图中结点的数量。非负整数m代表要图中有向边的数量。

第2行到第1+m行: a b p //每行两个整数:代表结点a到结点b有一条有向边(a->b),权值为p

Output Format

一个整数,由start到end的最短路径上边的总权值的大小。

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;
    edgeNode *head;

    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;
        nodes[temp1]->head = new edgeNode(temp2, temp3, nodes[temp1]->head);
    }

    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;
    edgeNode *p = nodes[i]->head;
    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;

class adjListGraph
{
public:
    adjListGraph(int vSize, const int d[]);
    void insert(int x, int y, int w);
    void spfa(int start, int end) const;
    ~adjListGraph();

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;
        edgeNode *head;

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

    int Vers, Edges;
    verNode *verList;

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

adjListGraph::adjListGraph(int vSize, const int d[])
{
    this->Vers = vSize;

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

adjListGraph::~adjListGraph()
{
    int i;
    edgeNode *p;

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

void adjListGraph::insert(int x, int y, int w)
{
    int u = x - 1, v = y - 1;
    verList[u].head = new edgeNode(v, w, verList[u].head);
    ++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;
    }
    adjListGraph graph(n, verarray);
    for (int i = 0; i < m; i++)
    {
        cin >> edgestart >> edgeend >> edgeweight;
        graph.insert(edgestart, edgeend, edgeweight);
    }
    graph.spfa(start, end);
    return 0;
}