{"id":279,"date":"2023-09-28T00:51:03","date_gmt":"2023-09-27T16:51:03","guid":{"rendered":"https:\/\/www.n-bc.top\/?p=279"},"modified":"2026-08-21T11:44:35","modified_gmt":"2026-08-21T03:44:35","slug":"%e5%8d%95%e6%ba%90%e6%9c%80%e7%9f%ad%e8%b7%af","status":"publish","type":"post","link":"https:\/\/www.n-bc.top\/?p=279","title":{"rendered":"\u5355\u6e90\u6700\u77ed\u8def"},"content":{"rendered":"\n

\u7ed9\u51fa\u4e00\u4e2a\u6709\u5411\u56fe\uff0c\u8bf7\u8f93\u51fa\u4ece\u67d0\u4e00\u70b9\u51fa\u53d1\u5230\u6240\u6709\u70b9\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u3002<\/span>

<\/hr>

\u8f93\u5165\u683c\u5f0f(Format Input)<\/h4>

\u7b2c\u4e00\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570N\u3001M\u3001S\uff0c\u5206\u522b\u8868\u793a\u70b9\u7684\u4e2a\u6570\u3001\u6709\u5411\u8fb9\u7684\u4e2a\u6570\u3001\u51fa\u53d1\u70b9\u7684\u7f16\u53f7\u3002 \u63a5\u4e0b\u6765M\u884c\u6bcf\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570Fi\u3001Gi\u3001Wi\uff0c\u5206\u522b\u8868\u793a\u7b2ci\u6761\u6709\u5411\u8fb9\u7684\u51fa\u53d1\u70b9\u3001\u76ee\u6807\u70b9\u548c\u957f\u5ea6(\u957f\u5ea6\u4e0d\u4f1a\u8d85\u8fc7100)\u3002<\/p>

\u8f93\u51fa\u683c\u5f0f(Format Output)<\/h4>

\u4e00\u884c\uff0c\u5305\u542bN\u4e2a\u7528\u7a7a\u683c\u5206\u9694\u7684\u6574\u6570\uff0c\u5176\u4e2d\u7b2ci\u4e2a\u6574\u6570\u8868\u793a\u4ece\u70b9S\u51fa\u53d1\u5230\u70b9i\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\uff08\u82e5S=i\u5219\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3a0\uff0c\u82e5\u4ece\u70b9S\u65e0\u6cd5\u5230\u8fbe\u70b9i\uff0c\u5219\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3a-1\uff09<\/p>

<\/hr>

\u8f93\u5165\u6837\u4f8b(Sample Input)\u00a0<\/h4>

4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4<\/p>

\u8f93\u51fa\u6837\u4f8b(Sample Output)<\/h4>

0 2 4 3<\/p>

<\/hr>

\u4ee3\u7801(Code)<\/strong><\/p>

#include<bits\/stdc++.h>
using namespace std;
struct point{
    int e,w;
}; 
vector<point>head[10010];
int n,m,s,dis[10010],used[10010];
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        head[x].push_back(point{y,z});
    }
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int Min=1e9,k=0;
        for(int j=1;j<=n;j++)
        {
            if(Min>dis[j]&&used[j]==0)
            {
                Min=dis[j],k=j;
            }
        }
        if(Min==1e9)\tbreak;
        used[k]=1;
        for(int j=0;j<head[k].size();j++)
        {
            int v=head[k][j].e;
            int va=head[k][j].w;
            if(dis[v]>dis[k]+va)\tdis[v]=dis[k]+va;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x7f7f7f7f)
        {
            cout<<-1<<\" \";
        }
        else
        {
            cout<<dis[i]<<\" \";
         } 
    }
    return 0;
}<\/code><\/pre><\/p>\n","protected":false},"excerpt":{"rendered":"
\u7ed9\u51fa\u4e00\u4e2a\u6709\u5411\u56fe\uff0c\u8bf7\u8f93\u51fa\u4ece\u67d0\u4e00\u70b9\u51fa\u53d1\u5230\u6240\u6709\u70b9\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u3002 \u8f93\u5165\u683c\u5f0f(Format Input) \u7b2c\u4e00\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570N\u3001M\u3001S\uff0c\u5206\u522b\u8868\u793a\u70b9\u7684\u4e2a\u6570\u3001\u6709\u5411\u8fb9\u7684\u4e2a\u6570\u3001\u51fa\u53d1\u70b9\u7684\u7f16\u53f7\u3002 \u63a5\u4e0b\u6765M\u884c\u6bcf\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570Fi\u3001Gi\u3001Wi …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[3,1],"tags":[],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-js","category-origin"],"_links":{"self":[{"href":"https:\/\/www.n-bc.top\/index.php?rest_route=\/wp\/v2\/posts\/279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.n-bc.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.n-bc.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.n-bc.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.n-bc.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=279"}],"version-history":[{"count":0,"href":"https:\/\/www.n-bc.top\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.n-bc.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.n-bc.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.n-bc.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}