Low C performance for TSP heuristic
Well, the first thing to do is extracting the distance-calculation and replacing the costly call to pow():

inline static double distance2(city* a, city* b) {
    double dx = a-&gt;x - b-&gt;x;
    double dy = a-&gt;y - b-&gt;y;
    return dx * dx + dy * dy;
}


Next, let's stop always copying the cities when not really needed.

Optionally, use a sentinel value (INFINITY) so we don't need to single out any candidate for nearest city.

Another nearly gratuitious change I did was starting with the last city given.

I suggest you also invest in slightly more spaces, they make things more readable, especially around operators.

The changed function:

double tsp(city* cities, int N) {
    double S = 0;
    for (int i = N; --i &gt; 0;) {
        double best_d2 = distance2(cities + i, cities + 0);
        int best_pos = 0;
        for(int j = i; --j &gt; 0;) {
            double d2 = distance2(cities + i, cities + j);
            if(d2 &lt; best_d2 || d2 == best_d2 &amp;&amp; cities[j].ind &lt; cities[best_pos].ind) {
                best_d2 = d2;
                best_pos = j;
            }
        }
        S += sqrt(best_d2);
        city temp = cities[best_pos];
        cities[best_pos] = cities[i - 1];
        cities[i - 1] = temp;
    }
    return S + sqrt(distance2(cities, cities + N - 1));
}