실패 한 SPFA

#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
int map[108][108];
//int path[108];
int dist[108];
int vis[108];
void spfa(int n,int s)
{
    int i, v;
    queueq;
    q.push(s);
    dist[s] = 0;
    vis[s] = 1;
    while(!q.empty())
    {
        v = q.front();
        q.pop();
        for(i = 1;i <= n; i++)
        {
            if(!vis[i] && map[v][i] != INF && dist[i] > dist[v] + map[v][i])
            {
                dist[i] = dist[v] + map[v][i];
                if(vis[i] == 0)
                {
                    q.push(i);
                    vis[i] = 1;
                }
            }
        }
    }
   printf("%d
",dist[n]); } int main() { int n, m, a, i, b, c; while(~scanf("%d %d",&n,&m)) { memset(vis,0,sizeof(vis)); memset(map,INF,sizeof(map)); //memset(path,0,sizeof(path)); memset(dist,0,sizeof(dist)); for(i = 1;i <= n;i++) { map[i][i] = 0; } for(i = 1;i <= m;i++) { scanf("%d %d %d",&a,&b,&c); map[a][b] = c; // path[b] = a; } spfa(b,1); } return 0; }

좋은 웹페이지 즐겨찾기